ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1009. K-ичные числа

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Рассмотрим 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