Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:

• 1010230 — правильное 7-значное число;
• 1000198 не является правильным числом;
• 0001235 — не 7-значное, а 4-значное число.

Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.

Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 1800.

Числа N и K в десятичной записи, разделенные переводом строки.

Искомое количество в десятичной записи.