eolymp
bolt
Try our new interface for solving problems
Problems

Числа

Числа

Time limit 2 seconds
Memory limit 32 MiB

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

  1. XN;

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

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

Input data

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

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

Output data

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

Examples

Input example #1
2 0
10
Output example #1
2