Числа

Дано три цілих числа N, a і b. Потрібно знайти залишок від ділення на число 1000000007 (10^9+7) кількості натуральних чисел X, для яких одночасно справджуються такі три умови:

1. X ≤ N;

2. X кратне 2^a;

3. сума цифр числа X кратна 2^b.

Вхідні дані

Перший рядок вхідного файлу містить 2 цілих числа: a та b (0 ≤ a ≤ 9, 0 ≤ b ≤ 9).

Другий рядок містить число N (1 ≤ N ≤ 10^5000).

Вихідні дані

Вихідний файл має містити одне число — залишок від ділення на число 1000000007 (10^9+7) кількості натуральних чисел X, для яких справджуються усі умови 1–3, подані вище.

Приклади