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

Ленточка

Ленточка

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

Есть ленточка, на которой может быть записано натуральное число, состоящее ровно из N цифр. Над ленточкой можно выполнить следующую операцию: разрезать ленточку между любыми двумя последовательными цифрами числа, не переворачивая, поменять местами получившиеся два куска, и склеить их снова. Ленточка считается красивой, если после этой операции на склеенной ленточке окажется то же самое число. Например, ленточка с числом 5656 является красивой, а 5665 – нет. Требуется найти количество различных чисел, которые при записи на ленточке делают ее красивой.

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

Программа считывает одно целое число: длину ленточки N. 1N1 000 007.

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

Необходимо вывести количество N-значных чисел, делающих ленточку "красивой", по модулю 1 000 007.

Пример

Входные данные #1
4 
Выходные данные #1
90
Автор Непомнящий Григорий
Источник Турнир Чемпионов, Винница 2010