题目描述

原题链接：Codeforces 1761D - Carry Bit。原出题人 $\tt{\color{black}{u}}{\color{red}{ nputdownable}}$，经其同意后加强并上传 loj。

注意，不仅修改了数据范围，题意也有改动。

设一个数 $v$ 的二进制表示中 $1$ 的个数为 $g(v)$。

设 $f(x,y)=g(x)+g(y)-g(x+y)$，也即 $x$ 与 $y$ 二进制相加时的进位数。

现给定 $N,k(k\le N)$，你要对所有 $n=k,k+1,\cdots,N$，求出

$$S(n,k)=\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}[f(i,j)=k] $$

答案对 $10^9+7$ 取模。

输入格式

一行两个整数，$N$ 和 $k$。

输出格式

为了避免输出量过大，我们采用如下方式输出。

设 $f_n=S(n,k)\bmod 1000000007$。

设 $g_n=nf_n$，且不取模（C++ 选手可使用 unsigned long long 类型计算并存储）。

你应当输出 $g_k\oplus g_{k+1}\oplus g_{k+2}\oplus\cdots\oplus g_N$，其中 $\oplus$ 表示按位异或运算。

3 1

36

3 0

64

998 244

630338983045

65537 65530

13776173599910

926878 926871

1105232236403512

1919810 114514

1431279937541241

数据范围与提示

对于 $100\%$ 的数据，$0\le k\le N\le2\times10^7$。

以下记 $r=N-k$。

子任务编号	子任务分值	$N$	$k$	特殊性质	子任务依赖
$1$	$2{\rm pts}$	$\le5$		$r=0$	无
$2$	$3{\rm pts}$			无	$1$
$3$	$5{\rm pts}$	$\le500$		$r=0$
$4$	$9{\rm pts}$			无	$2,3$
$5$	$5{\rm pts}$	$\le2000$		$r=0$	$3$
$6$	$13{\rm pts}$			无	$4,5$
$7$	$5{\rm pts}$	$\le100000$		$r=0$	$5$
$8$	$5{\rm pts}$			$r\le10$	$7$
$9$	$7{\rm pts}$			无	$6,8$
$10$	$8{\rm pts}$	$\le1000000$		$r=0$	$7$
$11$	$8{\rm pts}$			$r\le10$	$8,10$
$12$	$10{\rm pts}$			无	$9,11$
$13$	$5{\rm pts}$	$\le20000000$		$r=0$	$10$
$14$	$15{\rm pts}$			无	$12,13$