eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Слова-убийцы

Слова-убийцы

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

Агентство Федеральной Безопасности очень заинтересовано в лояльности своих спецагентов. Для обеспечения лояльности был разработан механизм слов-убийц: если агент перестаёт подчиняться приказам, то для его физического уничтожения достаточно произнести при нём вслух некоторое слово, которое активирует зашитую в мозге агента бомбу.

Чтобы бомба не была активирована случайно, слово-убийца должно быть достаточно специфическим: в нём должны встречаться только первые m букв латинского алфавита и оно должно являться k-повтором, то есть должно быть представимо в виде конкатенации k одинаковых слов. Более того, чтобы случайно не уничтожить лишних агентов, никакое собственное подслово этого слова не может являться k-повтором. Ваша задача — посчитать количество слов, пригодных для использования в качестве слов-убийц и состоящих не более чем из n букв.

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

В единственной строке через пробел записаны целые числа m, k, n (1m18; 2k5; 1n22).

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

Выведите искомое количество слов-убийц.

Пример

Входные данные #1
3 2 4
Выходные данные #1
9
Автор Алексей Самсонов
Источник Ural SU Contest. Petrozavodsk Winter Session, February 2009