Problem Description

Unagi received a sequence $S=\{S_1,S_2,...,S_N\}$ from Santa Rabbit for Christmas.

Unagi decided to find the sum of the numbers in the sequence.

The sequence $ S $ is generated by the following pseudocode:

input $ N $ input $ X,T,A,B,C $ for $ i $ = $1\ ...\ N$: $ S_i $ = $ X $ for $ j $ = $1\ ...\ T$: $X\ =\ (A*X\ +\ B)$ mod $ C $

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ T $ $ A $ $ B $ $ C $

• The first line contains an integer $N\ (1≦N≦10^6)$.
• The second line contains five integers $X,T,A,B,C\ (0≦X\ <\ C,\ 1≦T≦10^9,\ 0≦A\ <\ C,\ 0≦B\ <\ C,\ 1≦C≦10^9)$ separated by spaces.

Output Format

Output the sum of the numbers in the sequence $ S $. Add a newline at the end of the output.

Sample Input and Output

Sample Input #1

5
5 2 3 2 1000

Sample Output #1

1281

Sample Input #2

1000000
868183950 1000000000 209366437 803988878 999999937

Sample Output #2

499932726887669

Notes/Hints

Sample Explanation 1

The sequence is $\{5,53,485,373,365\}$, and the sum is $ 1281 $.

见题面 Input 部分

见题面 Output 部分