During the last covert operation, Captain Marvel managed to steal the coded
skrull secret message — string s. However, in the encoded form, it does not represent any useful information, so it must be decoded.
Despite the development of the Skrulls, their message encoding system is simple and well known:
• The digit d is selected before encoding the message (0 <= d <= 9)
• Message characters are read from left to right
• For each character of the message, its ASCII code is calculated (for example, for "a" it is 97, for
"b" — 98, "z" has — 122)
• If the code is three-digit, it is appended to the current encoded string as is, if
the code is two-digit, the number d is added to it in a random place and the result obtained
appends to the current encoded string (for example, if d = 3 and the current letter —
"a", the numbers 397, 937 or 973 can be added to the current encoded string)
• After processing all the letters, the result is the encoded string
The number d is usually sent along with the message, but Captain Marvel couldn't find it. However, she knows for sure that the original message consisted only of lowercase and uppercase Latin
lit. She understands that without the number d, it may not be possible to unambiguously decode the message, so first she wants to calculate how many different strings t, consisting of lowercase
and uppercase latin letters, such that, when encoded, the string s will be obtained. Since our heroine
cannot be completely sure that the message was completely intercepted, it is quite possible
that it cannot be decoded in any way.
Help our heroine — find the number of these strings modulo 109 + 7.
Input data format
The single line contains the encoded string s stolen by Captain Marvel
(3 <= |s| <= 105). It is guaranteed that the string s consists of only digits and that its length is a multiple of 3.
Output format
On a single line print a single number — the number of different strings consisting of lowercase and uppercase Latin letters that are encoded into the string s, modulo 109 + 7.
| Input |
Output |
| 988 |
2 |
| 100905 |
1 |
| 600 |
0 |
Note
In the first example, the encoded string can be obtained from "b" if d = 8, and also from "X" if d = 9.
In the second example, the encoded string can only be obtained from "dZ"; for d = 5.