Задачи
Ленточка
Ленточка
Есть ленточка, на которой может быть записано натуральное число, состоящее ровно из N цифр. Над ленточкой можно выполнить следующую операцию: разрезать ленточку между любыми двумя последовательными цифрами числа, не переворачивая, поменять местами получившиеся два куска, и склеить их снова. Ленточка считается красивой, если после этой операции на склеенной ленточке окажется то же самое число. Например, ленточка с числом 5656 является красивой, а 5665 – нет. Требуется найти количество различных чисел, которые при записи на ленточке делают ее красивой.
Входные данные
Программа считывает одно целое число: длину ленточки N. 1 ≤ N≤ 1 000 007.
Выходные данные
Необходимо вывести количество N-значных чисел, делающих ленточку "красивой", по модулю 1 000 007.
Пример
Входные данные #1
4
Выходные данные #1
90