В конце учебного года декан каждого факультета Хогвартса должен разместить итоговую сумму очков, набранных студентами своего факультета, на специальном магическом табло в Большом зале. Изначально сумма очков на табло для каждого факультета равна нулю. Для того, чтобы выставить на табло нужную сумму, деканы могут использовать лишь три заклинания:
1) «engorgio 1» (увеличивает сумму на табло на 1);
2) «engorgio 5» (увеличивает сумму на табло на 5);
3) «engorgio \(\times2\)» (увеличивает сумму на табло в 2 раза).
Профессор МакГонагалл знает, что она должна установить для факультета Гриффиндор на табло сумму очков, равную \(n\).
Сколько существует различных последовательностей применения заклинаний «engorgio», с помощью которых профессор сможет добиться желаемого результата на табло? При этом каждое применение заклинания в последовательности должно быть результативным, т.е. число на табло в результате взмаха волшебной палочки обязательно должно измениться.
Поскольку количество таких последовательностей может быть очень большим, ответ требуется дать по модулю \(10^9+7\).
Формат входных данных
Программа получает на ввод единственное целое неотрицательное число \(n\). Гарантируется, что \(0\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное число — количество различных последовательностей применения заклинаний «engorgio», позволяющих установить на табло число \(n\) при начальном значении 0.
| № | Входные данные | Выходные данные |
|
1
|
0
|
1
|
|
2
|
2
|
2
|
|
3
|
5
|
5
|
|
4
|
2048
|
233157015
|