This problem is a programming version of Problem 226 from projecteuler.net
For any real number , define as the distance from to its nearest integer.
Let be positive integers and consider the function defined on the real inteval by:
For example, when we get the blancmange function shown bellow
Given a polynomial , where are integers. Let
It can be proved that is a rational number, therefore we can write it as where and are integers.
In addition, the constraints on the inputs guarantee that is not divisible by the prime number .
In this case, find modulo ( is the the inverse of modulo ).
Input Format
The first line of each test file contains three space-separated integers , and .
The next line contains space-separated integers .
Constraints
- .
- .
- is not divisible by for all .
- .
- .
Output Format
Print your answer in one line.
Sample Input 0
2 2 0
1
Sample Output 0
502267905
Explanation 0
The graph of is shown in the statement.
, hence .
Sample Input 1
2 3 0
1
Sample Output 1
627834881
Explanation 1
Below is the graph of
, hence .
Sample Input 2
2 2 1
0 1
Sample Output 2
753401857
Explanation 2
The following is the graph of
, hence .
Sample Input 3
42 57 5
490 480 625 34 405 968
Sample Output 3
617014829