D. Дигорская последовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность, где каждый $$$i$$$-ый член последовательности задается формулой $$$F_i = F_{i-1} + i + F_{i-1}$$$. Где "$$$+$$$" — конкатенация (склеивание в буквальном смысле). Например, $$$F_1 = 1$$$, $$$F_2 = 121$$$, $$$F_3 = 1213121$$$. По заданному числу $$$n$$$ посчитаете количество цифр значения $$$F_n$$$. Поскольку ответ может быть большим, вывести его по модулю $$$10^9+7$$$.

Входные данные

В единственной строке дано натуральное число $$$n$$$, которое не превосходит $$$10^9$$$.

Выходные данные

Ответ на задачу по модулю $$$10^9+7$$$.

Примеры
Входные данные
2
Выходные данные
3
Входные данные
3
Выходные данные
7
Входные данные
4
Выходные данные
15