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