CF1761D Carry Bit

设 $f(x,y)$ 表示 $x+y$ 在二进制下的进位次数（即 $f(x,y)=g(x)+g(y)-g(x+y)$，其中 $g(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数）。 给定两个整数 $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

输出一个整数，表示答案对 $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)$。 由 ChatGPT 4.1 翻译