P17816 [ICPC 2019 Nanchang R] XOR Sum

The bitwise exclusive-or sum of a sequence $a_1,a_2,\cdots,a_n$ is defined as $a_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 $$ \sum_{k=1}^{t}\sum_{i=x}^{y} f(i, k) $$ where $f(i,k)$ is the bitwise exclusive-or sum of the sequence $1,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 $(10^9+7)$.

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

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