Numbers#7048
Given three integers , , and , your task is to determine the remainder when the count of natural numbers that meet the following conditions is divided by (10^9+7):
X \leq N;
is divisible by 2^{a};
The sum of the digits of is divisible by 2^{b}.
The first line of the input contains two integers: and (0 \leq a \leq 9, 0 \leq b \leq 9).
The second line contains the integer (1 \leq N \leq 10^{5000}).
The output should be a single number: the remainder when the count of natural numbers that satisfy all the conditions above is divided by (10^9+7).
Example 1