Bessie's Phone Keypress Permutations

Bessie got a new phone whose nine keys are arranged as follows:

1 2 3
4 5 6
7 8 9

While in a hurry, Bessie tries to dial a phone number by pressing several keys at once with one hoof in order to save time. In a single press she can press:

• a single key,
• a pair of keys that share a common edge (there are in total $12$ possible pairs),
• or a group of four keys that form a square (namely, the keys {1,2,4,5}, {2,3,5,6}, {4,5,7,8} or {5,6,8,9}).

When Bessie presses multiple keys at once, the order in which these keys are registered is arbitrary. For instance, if Bessie intended to dial the number 123659874 using the following presses:

1. pressing keys 1 and 2 together,
2. pressing key 3,
3. pressing keys 6, 5, 9 and 8 together,
4. pressing keys 7 and 4 together,

the final sequence registered could be 123596847 or 213659874 (among other possibilities).

Given the sequence of digits that Bessie actually input, determine the number of different phone numbers she might have intended. Since the answer can be large, output it modulo $10^9+7$.

Note that when Bessie presses multiple keys simultaneously, the intended order of the digits (i.e. the phone number she meant to dial) is lost; any permutation of the pressed keys could be the intended ordering. For a two‐key press the intended phone number can have either ordering (2 possibilities) and for a four‐key press there are $4! = 24$ possibilities. Single key presses contribute exactly 1 possibility.

inputFormat

The input consists of a single line containing a string s of digits (each digit between 1 and 9), representing the sequence that was actually entered by Bessie.

outputFormat

Output a single integer which is the number of possible phone numbers Bessie might have intended to dial, modulo $10^9+7$.

sample

1

1