Коров'ячі гімнасти
Стомившись від життя на фермі, корови вирішили приєднатися до бродячого цирку, де вони готують нове шоу.Сцена для шоу складається з n платформ, розташованих по колу. На кожній платформі від 1 до n корів утворюють стек (корова стоїть на корові). За сигналом головного на манежі, всі стеки одночасно "падають" за годинниковою стрілкою: нижня корова стека залишається на місці, корова над нею переміщується на одну платформу за годинниковою стрілкою, наступна корова - на дві платформи і так далі. У результаті утворюються нові стеки корів.
Головний на манежі вважає, що шоу буде кращим, якщо після падіння стеків новий стек на кожній платформі міститиме таку ж кількість корів, як і початковий стек. Ми називаємо конфігурацію стеків на манежі "магічною", якщо вона відповідає цій умові. Потрібно обчислити кількість "магічних" конфігурацій. Оскільки це число може бути дуже великим, виведіть його залишок по модулю 10^9 + 7.
Дві конфігурації вважаються різними, якщо існує платформа, на якій у цих двох конфігураціях різна кількість корів.
Вхідні дані
Одне ціле число n (1 ≤ n ≤ 10^12).
Вихідні дані
Одне ціле число - кількість магічних конфігурацій по модулю 10^9 + 7.
Приклад
Для n = 4, можливі магічні конфігурації: (1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3) і (3, 2, 3, 2).