I am trying to become a good guy, giving contestants as little pain as possible. So, this problem is very simple and easy, rejoice!
You will be given Q queries and an integer X. In each query, you will be given four integers A, B, C and M. For each query, you just have to find
$\displaystyle \sum_{\displaystyle i=0}^{\displaystyle 100000} X^{\displaystyle Z_i} \pmod {10^{\displaystyle 9}+7}$
where $Z_{\displaystyle i} = AZ_{\displaystyle i-1} + C \pmod M$ and $Z_{\displaystyle 0} = B$.
Simple, right? Thank me later. 🙂
Input
Input starts with two space-separated integers Q (1 ≤ Q ≤ 103) and X (1 ≤ X ≤ 109), in a single line.
Each of the following Q lines will represent a query, containing four space-separated integers A, B, C (0 ≤ A, B, C < M) and M (1 ≤ M ≤ 232) in each line.
Output
For each query, print the answer in a single separate line as shown in the samples.
Samples
| Input | Output |
|---|---|
1 1 1 2 3 4 | 100001 |
| Input | Output |
|---|---|
2 2 0 1 1 5 0 2 2 1000000 | 200002 400004 |
