Задачі
Стрічка
Стрічка
Є стрічка, на якій може бути записане натуральне число, що складається рівно з \textbf{N} цифр. Над стрічкою можна виконати наступну операцію: розрізати стрічку між довільними двома послідовними цифрами числа, не перевертаючи, поміняти місцями отримані дві частини, і зклеїти їх знову. Стрічка вважається "\textit{\textbf{красивою}}", якщо після цієї операції на зклеєній стрічці виявиться те ж саме число. Наприклад, стрічка з числом \textbf{5656} - красива, а \textbf{5665} -- ні. Потрібно знайти кількість різних чисел, які при запису на стрічці роблять її красивою.
\InputFile
Програма зчитує одне ціле число: довжину стрічки \textit{\textbf{N}}. \textbf{1} ≤ \textit{\textbf{N}}\textit{ }≤ \textbf{1 000 007}.
\OutputFile
Необхідно вивести кількість \textit{\textbf{N}}-значних чисел, які роблять стрічку "\textit{\textbf{красивою}}", по модулю \textbf{1 000 007}.
Вхідні дані #1
4
Вихідні дані #1
90