Числа

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

1. X ≤ N;

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

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

Входные данные

Первая строка входных данных содержит два целых числа: a и b (0 ≤ a ≤ 9, 0 ≤ b ≤ 9).

Вторая строка содержит число N (1 ≤ N ≤ 10^5000).

Выходные данные

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

Примеры