Carry Bit

题意翻译

设 $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\neq b$，$(a,b)$ 和 $(b,a)$ 被认为是两个不同的对。 由于这个数可能很大，对它取模 $10^9+7$ 输出。

题目描述

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 < 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 $ .

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3 1

输出样例 #1

15

输入样例 #2

3 0

输出样例 #2

27

输入样例 #3

998 244

输出样例 #3

573035660

说明

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} $ $ </p><p>So $ f(7,4)=1 $ , $ f(5,1)=1 $ and $ f(5,3)=3 $ .</p><p>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)$.

题目大意：
给定一个函数 $ 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 \neq b $，$ (a,b) $ 和 $ (b,a) $ 被认为是两个不同的对。

由于这个数可能很大，最后的结果需要取模 $ 10^9+7 $ 后输出。

输入输出数据格式：
- 输入格式：每行包含两个整数 $ n $ 和 $ k $（$ 0 \leq k < n \leq 10^6 $）。
- 输出格式：输出一个整数，即满足条件的有序对 $ (a,b) $ 的个数模 $ 10^9+7 $ 的结果。

输入输出样例：
- 输入样例 #1：3 1
输出样例 #1：15
- 输入样例 #2：3 0
输出样例 #2：27
- 输入样例 #3：998 244
输出样例 #3：573035660题目大意： 给定一个函数 $ 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 \neq b $，$ (a,b) $ 和 $ (b,a) $ 被认为是两个不同的对。 由于这个数可能很大，最后的结果需要取模 $ 10^9+7 $ 后输出。 输入输出数据格式： - 输入格式：每行包含两个整数 $ n $ 和 $ k $（$ 0 \leq k < n \leq 10^6 $）。 - 输出格式：输出一个整数，即满足条件的有序对 $ (a,b) $ 的个数模 $ 10^9+7 $ 的结果。 输入输出样例： - 输入样例 #1：3 1 输出样例 #1：15 - 输入样例 #2：3 0 输出样例 #2：27 - 输入样例 #3：998 244 输出样例 #3：573035660