Məsələlər
Counting Amusing Numbers
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 \textbf{2N}-digit integer \textbf{X} (possibly with leading zeroes) amusing if two \textbf{N}-digit integers \textbf{a} and \textbf{b} (again, possibly with leading zeroes) exist such that \textbf{a} + \textbf{b} = \textbf{10^N} and \textbf{S_d}(\textbf{X}) = \textbf{S_d}(\textbf{a}) + \textbf{S_d}(\textbf{b}) holds for every digit \textbf{d}, where \textbf{S_d}(\textbf{P}) (\textbf{0 }≤ \textbf{d }≤ \textbf{9}) is the number of occurrences of digit \textbf{d} in the decimal representation of \textbf{P}. For example, numbers \textbf{46} (\textbf{4} + \textbf{6}= \textbf{10^1}), \textbf{9820} (\textbf{98} + \textbf{02} = \textbf{10^2}) and \textbf{08362090} (\textbf{6020} + \textbf{3980} = \textbf{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 \textbf{10^9} + \textbf{7}.
\InputFile
The only line contains a non-empty sequence of digits and question marks. The length of the sequence is even and doesn't exceed \textbf{10^5}. The number of question marks doesn't exceed \textbf{1000}.
\OutputFile
Print the sought number of ways modulo \textbf{10^9} + \textbf{7}.
Giriş verilənləri #1
2?4?
Çıxış verilənləri #1
4