Учёные в одной секретной биологической лаборатории вывели новый уникальный вид бактерий, над размножением которых биологи имеют полный контроль.
В начальный момент времени (\(t=0\) сек) популяция бактерий состоит всего лишь из двух особей. Далее учёные собираются применить программу размножения бактерий, чтобы численность популяции в результате составляла ровно \(n\) особей. Программа размножения состоит из отдельных шагов, каждый из которых выполняется за 1 сек:
1) увеличить число бактерий в популяции на 1;
2) увеличить число бактерий в популяции на 10;
3) увеличить число бактерий в популяции в 2 раза.
Сколько существует подходящих учёным программ размножения бактерий? Поскольку количество таких программ может быть очень большим, ответ требуется дать по модулю \(10^9+7\).
Формат входных данных
Программа получает на ввод единственное натуральное число \(n\). Гарантируется, что \(2\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное число — количество различных программ размножения бактерий, позволяющих учёным получить популяцию из \(n\) особей, взятое по модулю \(10^9+7\).
| № | Входные данные | Выходные данные |
|
1
|
2
|
1
|
|
2
|
6
|
3
|
|
3
|
12
|
11
|
|
4
|
1024
|
411603887
|