D. Carry Bittime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet 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.InputThe only line of each test contains two integers n and k (0\leq k<n\leq 10^6).OutputOutput a single integer  — the answer modulo 10^9+7.ExamplesInput
3 1
Output
15
Input
3 0
Output
27
Input
998 244
Output
573035660
NoteHere 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).
3 1

15 
['combinatorics', 'math', '*2100']