Ленточка

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

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

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

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

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

Примеры