- All Contests
- ProjectEuler+
- Project Euler #226: A Scoop of Blancmange

# Project Euler #226: A Scoop of Blancmange

# Project Euler #226: A Scoop of Blancmange

_{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
```