Carry Bit
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 2100
Tags: combinatorics, math

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

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

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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)$$$.

Example input:
3 1

Example output:
15

Example input:
3 0

Example output:
27

Editorial:
Hint 1: Try to solve the problem in $$$O(nk)$$$ using DP.
Hint 2: There is no need for DP.
Hint 3: You can consider enumerating the bits to carry, and then counting.
Let $$$a_i$$$ represents the $$$i$$$-th bit of $$$a$$$ in binary representation (that is, $$$2^i \times a_i=a \wedge 2^i$$$) and define $$$b_i$$$ similarly.
If you decide which bits to carry ahead, you will find that every bit of $$$a,b$$$ is independent (because whether the previous bit carries or not is decided), so you can use the multiplication principle to count.
Therefore, in the remaining tutorial, we should determine the carries first and then count the number of options of $$$a_i,b_i$$$ meeting the constraints of carries.
Define array $$$c$$$ as our decided carry plan, $$$c_i=1$$$ indicates that the $$$i$$$-th bit is carried, and define $$$c_{-1}$$$ as $$$0$$$.
Notice that $$$c_i=a_i \vee b_i \vee c_{i-1}$$$.
Ponder each bit, we will notice that if
• $$$c_i=c_{i-1}=0$$$, $$$(a_i,b_i)$$$ can be $$$(0,0),(0,1),(1,0)$$$.
• $$$c_i=c_{i-1}=1$$$, $$$(a_i,b_i)$$$ can be $$$(1,1),(0,1),(1,0)$$$.
• $$$c_i=1$$$ and $$$c_{i-1}=0$$$, $$$(a_i,b_i)$$$ must be $$$(1,1)$$$.
• $$$c_i=0$$$ and $$$c_{i-1}=1$$$, $$$(a_i,b_i)$$$ must be $$$(0,0)$$$.
That means that pair $$$(a_i,b_i)$$$ has $$$3$$$ options if $$$c_i=c_{i-1}$$$, and pair $$$(a_i,b_i)$$$ has $$$1$$$ options if $$$c_i\neq c_{i-1}$$$.
So if array $$$c$$$ has $$$q$$$ positions that $$$c_i\neq c_{i-1}$$$ ( $$$0 \leq i < n$$$, remember we define $$$c_{-1}$$$ as $$$0$$$ ), the count of pair $$$(a,b)$$$ is $$$3^{n-q}$$$.
Now we can enumerate $$$q$$$, and count the number of $$$c$$$ has $$$q$$$ positions that $$$c_i\neq c_{i-1}$$$.
The new problem equals a typical binomial problem.
Notice that for every $$$q$$$, a valid $$$c$$$ should have $$$\lfloor \frac{q}{2} \rfloor$$$ segment of consecutive $$$1$$$s and $$$\lceil \frac{q}{2} \rceil$$$ segment of consecutive $$$0$$$s if we seen $$$c_{-1}$$$ as a normal bit (so that we have $$$n-k+1$$$ zeros).
The number of solutions that divide $$$a$$$ elements into $$$b$$$ segments is $$$\binom{a-1}{b-1}$$$.
Therefore the answer of each $$$q$$$ is $$$3^{n-q} \times \binom{k-1}{\lfloor \frac{q}{2} \rfloor-1} \times \binom{(n-k+1)-1}{\lceil \frac{q}{2} \rceil-1}$$$, and we can calculate it in $$$\Theta(1)$$$.
Add them all and you can find the answer in $$$\Theta(n)$$$.