← 返回题目列表

Codeforces · 1761/D

D. 进位位

中文机器翻译题面 查看原题

设 $$$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 < 2^n$$$ 且 $$$f(a,b)$$$ 等于 $$$k$$$ 的有序对 $$$(a,b)$$$ 的数量。请注意,对于 $$$a\ne b$$$,$$$(a,b)$$$ 和 $$$(b,a)$$$ 被视为两个不同的对。

由于这个数字可能很大,因此输出它对 $$$10^9+7$$$ 取模。

输入

每个测试的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$0\leq k<n\leq 10^6$$$)。

输出

输出一个整数——答案以 $$$10^9+7$$$ 为模。

示例

输入 #1

3 1

输出 #1

15

输入 #2

3 0

输出 #2

27

输入 #3

998 244

输出 #3

573035660

注意

下面是一些理解carry的例子:

$$$$$$ \begin{对齐} &\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{数组} \end{对齐} $$$$$$

所以$$$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)$$$。