33OJ
登录 注册

#P17816. [ICPC 2019 Nanchang R] XOR Sum

    ID: 20415 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数学2019数论中国剩余定理 CRT快速傅里叶变换 FFT位运算快速数论变换 NTTICPC拉格朗日插值法

[ICPC 2019 Nanchang R] XOR Sum

Problem Description

The bitwise exclusive-or sum of a sequence a1,a2,⋯ ,ana_1,a_2,\cdots,a_n is defined as a1⊕a2⊕⋯⊕ana_1 \oplus a_2 \oplus \cdots \oplus a_n where ⊕\oplus represents the bitwise exclusive-or.

Now you are asked to calculate the value of

∑k=1t∑i=xyf(i,k)\sum_{k=1}^{t}\sum_{i=x}^{y} f(i, k)

where f(i,k)f(i,k) is the bitwise exclusive-or sum of the sequence 1,2,3,⋯ ,ik−2,ik−1,ik1,2,3,\cdots,i^k-2,i^k-1,i^k.

Since the answer can be very large, you only need to output the answer modulo (109+7)(10^9+7).

Input Format

The only line contains three integers t (1≤t≤100000),xt~(1 \le t \le 100000), x and y (1≤x≤y≤1018)y~(1 \le x\le y \le 10^{18}) described as above.

Output Format

Output an integer in a line indicating the answer modulo (109+7)(10^9+7).

1 2 7
15
3 2 7
363
7 2 7
358035