A telegraph message is a string of characters, each either a digit 0-9 or the wildcard *. A wildcard stands for exactly one unknown digit from 1 to 9 (never 0). To decode a fully-resolved digit string, split it left to right into groups, each being a single digit forming 1-9 or two adjacent digits forming 10-26, with no leading zero in any group (so a 0 can only appear as the second digit of 10 or 20). The letters are 1 -> A, ..., 26 -> Z.
Count the total number of (wildcard resolution, decoding) outcomes: that is, over all ways to replace each * with a digit 1-9, sum the number of valid decodings of the resulting digit string. Print the total modulo 1000000007.
Input format
A single line: the message, consisting of characters 0-9 and *.
Output format
A single integer: the total number of decodings across all wildcard resolutions, taken modulo 1000000007.
Constraints
- 1 <= length of the message <= 15
- Each character is a digit
0-9or*. - The message contains at most 5 wildcard characters.