F. Крош и сумма ряда 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крошу в качестве нового домашнего задания по математике задали посчитать следующую сумму ряда: $$$\sum\limits_{n = 1}^{\infty} \frac{(C_n^k) ^ 2}{2^n}$$$, где $$$k$$$ - заданное число. Помогите ему решить эту задачу, для данного $$$k$$$ выведите сумму ряда. Гарантируется, что ответ - целое число. Выведите его по простому модулю $$$10^9+7$$$.

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

Вам дано число $$$0 \le k \le 10^6$$$.

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

Выведите ответ по модулю $$$10^9+7$$$.

Пример
Входные данные
2
Выходные данные
26
Примечание

$$$C_n^k$$$ – число сочетаний из $$$n$$$ по $$$k$$$.