Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

I Am Good 2.0

By Zeronfinity · Limits 3s, 512 MB

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

InputOutput
1 1
1 2 3 4

100001

InputOutput
2 2
0 1 1 5
0 2 2 1000000

200002
400004


Statistics

35% Solution Ratio

EgorKulikovEarliest, Feb '20

hafiz_samratFastest, 1.3s

Wojciech.324122Lightest, 655 kB

omar24Shortest, 858B

Editorial

With an increased time limit of ~12s, the problem would be easily solvable using fast/binary exponen...

Related Contests

 Criterion 2020 Round 3Ended Feb '20