Назовём конечную последовательность натуральных чисел красивой, если она начинается с единицы и каждый её член, кроме первого, больше предыдущего на 1, на 7 или в 2 раза. Последовательность, состоящая из одной единицы, также является красивой.
Напишите программу, вычисляющую количество различных красивых последовательностей, заканчивающихся числом \(n\).
Поскольку количество таких последовательностей может быть очень большим, ответ требуется вывести по модулю \(10^9+7\).
Формат входных данных
На вход программе подаётся единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное число — количество различных красивых последовательностей, заканчивающихся числом \(n\), взятое по модулю \(10^9+7\).
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
1
|
|
3
|
17
|
52
|
|
4
|
1024
|
360748210
|