Counting Amusing Numbers
Do you think that counting is easy? This is not the case when you don't fully understand objects that you are counting.
Let's call a 2N-digit integer X (possibly with leading zeroes) amusing if two N-digit integers a and b (again, possibly with leading zeroes) exist such that a + b = 10^N and S_d(X) = S_d(a) + S_d(b) holds for every digit d, where S_d(P) (0 ≤ d ≤ 9) is the number of occurrences of digit d in the decimal representation of P. For example, numbers 46 (4 + 6 = 10^1), 9820 (98 + 02 = 10^2) and 08362090 (6020 + 3980 = 10^4) are amusing.
You are given a sequence of digits and question marks of an even length. Find the number of ways to replace question marks with digits to get an amusing number, modulo 10^9 + 7.
Input
The only line contains a non-empty sequence of digits and question marks. The length of the sequence is even and doesn't exceed 10^5. The number of question marks doesn't exceed 1000.
Output
Print the sought number of ways modulo 10^9 + 7.