Numbers

Given three integers (N), (a), and (b), your task is to determine the remainder when the count of natural numbers (X) that meet the following conditions is divided by (1000000007) ((10^9+7)):

1. (X $\le$ N);

2. (X) is divisible by (2^a);

3. The sum of the digits of (X) is divisible by (2^b).

Input

The first line of the input contains two integers: (a) and (b) ((0 $\le$ a $\le$ 9), (0 $\le$ b $\le$ 9)).

The second line contains the integer (N) ((1 $\le$ N $\le$ 10^5000)).

Output

The output should be a single number: the remainder when the count of natural numbers (X) that satisfy all the conditions above is divided by (1000000007) ((10^9+7)).

Examples