H. Последовательность Аслана
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
16 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аслан очень вдохновился последовательностью Фибоначчи и решил придумать свою рекуррентную последовательнось, которую определил следующим образом: $$$$$$F_1 = 1,$$$$$$$$$$$$F_2=1,$$$$$$ $$$$$$F_n = 2\times F_{n-1} + 3 \times F_{n-2} + n.$$$$$$ Помогите Аслану по заданному $$$n$$$ вычислить $$$n$$$ -й член такой последовательности.

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

На вход подается число $$$n (1 \leq n \leq 10^9)$$$.

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

Выведите единственное число — ответ на задчу по модулю $$$10^9+7$$$.

Примеры
Входные данные
3
Выходные данные
8
Входные данные
7
Выходные данные
682