Рассмотрим
N-значные числа в системе счисления с основанием
K. Будем считать число
правильным, если его
K-ичная запись не содержит двух подряд идущих нулей. Например:
- 1010230 — правильное 7-значное число;
- 1000198 не является правильным числом;
- 0001235 — не 7-значное, а 4-значное число.
Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.
Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.
Исходные данные
Числа N и K в десятичной записи, разделенные переводом строки.
Результат
Искомое количество в десятичной записи.
Пример
исходные данные | результат |
---|
2
10
| 90
|
Источник задачи: Чемпионат УрГУ 1997