Problems
Ленточка
Ленточка
Есть ленточка, на которой может быть записано натуральное число, состоящее ровно из \textit{\textbf{N}} цифр. Над ленточкой можно выполнить следующую операцию: разрезать ленточку между любыми двумя последовательными цифрами числа, не переворачивая, поменять местами получившиеся два куска, и склеить их снова. Ленточка считается красивой, если после этой операции на склеенной ленточке окажется то же самое число. Например, ленточка с числом \textbf{5656} является красивой, а \textbf{5665} -- нет. Требуется найти количество различных чисел, которые при записи на ленточке делают ее красивой.
\InputFile
Программа считывает одно целое число: длину ленточки \textit{\textbf{N}}. \textbf{1} ≤ \textit{\textbf{N}}\textit{ }≤ \textbf{1 000 007}.
\OutputFile
Необходимо вывести количество \textit{\textbf{N}}-значных чисел, делающих ленточку "\textbf{красивой}", по модулю \textbf{1 000 007}.
Input example #1
4
Output example #1
90