CF1761D.Carry Bit

Let $f(x,y)$ be the number of carries of $x+y$ in binary (i. e. $f(x,y)=g(x)+g(y)-g(x+y)$, where $g(x)$ is the number of ones in the binary representation of $x$).

Given two integers $n$ and $k$, find the number of ordered pairs $(a,b)$ such that $0 \leq a,b \lt 2^n$, and $f(a,b)$ equals $k$. Note that for $a\ne b$, $(a,b)$ and $(b,a)$ are considered as two different pairs.

As this number may be large, output it modulo $10^9+7$.

设 $f(x,y)$ 表示 $x+y$ 在二进制加法中产生的进位次数（即 $f(x,y)=g(x)+g(y)-g(x+y)$，其中 $g(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数）。

给定两个整数 $n$ 和 $k$，求满足 $0 \leq a,b \lt 2^n$ 且 $f(a,b) = k$ 的有序对 $(a,b)$ 的个数。注意：当 $a\ne b$ 时，$(a,b)$ 与 $(b,a)$ 被视为两个不同的有序对。

由于该数目可能很大，请输出其对 $10^9+7$ 取模的结果。

The only line of each test contains two integers $n$ and $k$ ($0\leq k \lt n\leq 10^6$).

每组测试数据仅包含一行，其中有两个整数 $n$ 和 $k$（$0\leq k \lt n\leq 10^6$）。

Output a single integer — the answer modulo $10^9+7$.

输出一个整数——答案对 $10^9+7$ 取模的结果。

Here are some examples for understanding carries:

\\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}

So $f(7,4)=1$, $f(5,1)=1$ and $f(5,3)=3$.

In the first test case, all the pairs meeting the constraints are $(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)$.

以下是一些关于进位的理解示例：

$$\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)$。