Пусть \(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\).
Примечание
Вот несколько примеров для понимания переносов:
\(\) \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)\).