Стрічка

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

Вхідні дані

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

Вихідні дані

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

Приклади