#P17703. [ICPC 2019 Nanjing R] Observation
[ICPC 2019 Nanjing R] Observation
Problem Description
As an astronomer, Alice pilots her spaceship to observe an unknown object in the universe. This object can be viewed as a point in the space in a common theoretical model since its size is significantly smaller than the viewing distance.
Building a space rectangular coordinate system centred at the object, a possible perfect observing position is such which locals at an integral point. Alice records the number of perfect observing positions whose viewing distances are equal to as .
Now, given a permitted range of viewing distance, a test coefficient and a large prime number , you are asked to calculate $\Big(\sum\limits_{d=L}^{R} (f_d \text{ xor } K)\Big) \pmod{P}$ to explore the risk factor.
Input Format
The first line contains an integer representing the number of test cases.
For each test case, an only line contains four integers and described as above, where , , the prime number satisfies and .
Output Format
For each test case, print a line which contains an integer representing the risk factor inquired.
2
1 1 0 11
1 1 1 11
6
7