# 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_i=0}^100000} X^Z_i} \pmod {10^9}+7$

where $Z_i} = AZ_i-1} + C \pmod$ and $Z_0} =$.

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

### Submit 