Є стрічка, на якій може бути записане натуральне число, що складається рівно з N цифр. Над стрічкою можна виконати наступну операцію: розрізати стрічку між довільними двома послідовними цифрами числа, не перевертаючи, поміняти місцями отримані дві частини, і зклеїти їх знову. Стрічка вважається "красивою", якщо після цієї операції на зклеєній стрічці виявиться те ж саме число. Наприклад, стрічка з числом 5656 - красива, а 5665 – ні. Потрібно знайти кількість різних чисел, які при запису на стрічці роблять її красивою.
Програма зчитує одне ціле число: довжину стрічки N. 1 ≤ N ≤ 1 000 007.
Необхідно вивести кількість N-значних чисел, які роблять стрічку "красивою", по модулю 1 000 007.