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