H. Simple XOR Problem
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Since Nagasaki Soyo claimed that she would do anything, she was given the simple XOR problem. Help her!

You're given four integers $$$l$$$, $$$r$$$, $$$y$$$, and $$$k$$$. Calculate:

$$$$$$ \sum_{x=l}^{r}\left(x\oplus y\right)^k\pmod{(10^{9}+7)} $$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

Input

The only line contains four integers $$$l$$$, $$$r$$$, $$$y$$$, and $$$k$$$ ($$$1\le l\le r\le 10^9$$$, $$$1\le y\le 10^9$$$, $$$1\le k\le 10^6$$$).

Output

Output one integer indicating the result of the formula above.

Examples
Input
1 10 1 1
Output
55
Input
114 514 1919 810
Output
353713127