Иван-Царевич вышел на бой со Змеем Горынычем, у которого в начале сражения (\(t=0\) мин) было \(n\) голов. Василиса Премудрая предупредила Ивана, что Змей потеряет силу и будет повержен, только если у него останется ровно одна голова: ни больше, ни меньше.
У Ивана есть три приёма, каждый из которых занимает ровно 1 мин:
1) удар мечом — Змей теряет 1 голову;
2) удар булавой — Змей теряет 5 голов;
3) заклятие Василисы — у Змея остаётся только половина голов с округлением вниз (из \(x\) голов остаётся \(\displaystyle\left\lfloor \frac{x}{2} \right\rfloor\) голов).
Сколько существует последовательностей приёмов, с помощью которых Иван-Царевич сможет одолеть Змея Горыныча? Поскольку количество таких последовательностей может быть очень большим, ответ требуется дать по модулю \(10^9+7\).
Формат входных данных
Программа получает на ввод единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное число — количество последовательностей приёмов, с помощью которых Иван-Царевич сможет одолеть Змея Горыныча, взятое по модулю \(10^9+7\).
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
3
|
3
|
|
3
|
7
|
16
|
|
4
|
1024
|
674051552
|