D. Битовые переносы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$f(x,y)$$$  — число переносов при двоичном сложении $$$x+y$$$ (т. е. $$$f(x,y)=g(x)+g(y)-g(x+y)$$$, где $$$g(x)$$$  — количество единиц в двоичном представлении $$$x$$$).

Для данных двух целых чисел $$$n$$$ и $$$k$$$, найдите количество упорядоченных пар $$$(a,b)$$$ таких, что $$$0 \leq a,b < 2^n$$$, а $$$f(a,b)$$$ равно $$$k$$$. Обратите внимание, что для $$$a\ne b$$$, $$$(a,b)$$$ и $$$(b,a)$$$ считаются как две разные пары.

Поскольку это число может быть большим, выведите его по модулю $$$10^9+7$$$.

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

Единственная строка каждого теста содержит два целых числа $$$n$$$ и $$$k$$$ ($$$0\leq k<n\leq 10^6$$$).

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

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

Примеры
Входные данные
3 1
Выходные данные
15
Входные данные
3 0
Выходные данные
27
Входные данные
998 244
Выходные данные
573035660
Примечание

Вот несколько примеров для понимания переносов:

$$$$$$ \begin{aligned} &\begin{array}{r} 1_{\ \ }1_{\ \ }1\\ +\ _{1}1_{\ \ }0_{\ \ }0\\ \hline \ 1_{\ \ }0_{\ \ }1_{\ \ }1 \end{array} &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{\ \ }0_{\ \ }0_{1}1\\ \hline \ 0_{\ \ }1_{\ \ }1_{\ \ }0 \end{array} & &\begin{array}{r} \ 1_{\ \ }0_{\ \ }1\\ +\ _{1}0_{1}1_{1}1\\ \hline \ 1_{\ \ }0_{\ \ }0_{\ \ }0 \end{array} \end{aligned} $$$$$$

Итак, $$$f(7,4)=1$$$, $$$f(5,1)=1$$$ и $$$f(5,3)=3$$$.

В первом примере все пары, удовлетворяющие ограничениям, это $$$(1,1),(1,5),(2,2),(2,3),(3,2),(4,4),(4,5),(4,6),(4,7),(5,1),(5,4),(5,6),(6,4),(6,5),(7,4)$$$.