题目描述

原题链接：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$，求出

答案对 $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$。