Коров'ячі гімнастки#10416
Втомившись від життя на фермі, корови продали все своє майно і приєдналися до трупи мандрівного цирку. Досі коровам діставалися прості номери: жонглювання смолоскипами, ходіння по канату, їзда на одноколісному велосипеді — нічого такого, з чим не впоралася б спритна корова. Однак директор цирку хоче поставити до наступної вистави значно ефектніший номер.
Сцена для нового номера складається з платформ, розташованих по колу. На кожній платформі від до корів мають утворити вежу, стаючи одна на одну. За сигналом директора всі вежі повинні одночасно впасти за годинниковою стрілкою: нижня корова у вежі залишається на місці, корова над нею переміщується на одну платформу за годинниковою стрілкою, наступна корова — на дві платформи за годинниковою стрілкою і так далі. Будучи досвідченими гімнастками, корови впевнені, що впораються з технічним боком номера. Падаючи, вежі не заважають одна одній, тому кожна корова приземляється на призначену їй платформу. Всі корови, що приземлилися на одну й ту саму платформу, утворюють нову вежу, яка вже не падає.
Директор вважає, що номер буде особливо ефектним, якщо після падіння нова вежа на кожній платформі міститиме стільки ж корів, скільки було в початковій вежі на цій платформі. Назвемо конфігурацію висот веж чарівною, якщо вона задовольняє цю умову. Допоможіть коровам підрахувати кількість чарівних конфігурацій. Оскільки це число може бути дуже великим, виведіть його за модулем 10^9 + 7.
Дві конфігурації вважаються різними, якщо хоча б на одній платформі в них знаходиться різна кількість корів.
Одне ціле число n~(1 \le n \le 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).
Приклад 1