THICC '17 P2 - Molly and Product

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M
Python 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Molly has a math addiction. For her birthday, she receives a sequence of length N defined by A_i = (A_{i-1} \times B) \bmod M. Given the value of A_0, help Molly find the sum of all pairwise products, mod 10^9+7.

Input Specification

The first and only line of input will contain N, A_0, B, and M, each space-separated.

Output Specification

The output should contain a single integer, the sum of all pairwise products, mod 10^9+7.

Constraints

For all subtasks,
1 \le A_0, B, M \le 10^9

Subtask 1 [40%]:

1 \le N \le 10^3

Subtask 2 [40%]:

1 \le N \le 10^5

Subtask 3 [20%]:

1 \le N \le 10^7

Sample Input

3 6 3 100

Sample Output

2808

Explanation for Sample Output

The three numbers are 6, 18, and 54. Their pairwise products are 6 \times 18 = 108, 6 \times 54 = 324, 18 \times 6 = 108, 18 \times 54 = 972, 54 \times 6 = 324 and 54 \times 18 = 972 and their sum is 2808.


Comments

There are no comments at the moment.