While she was living in the Spiral King's castle, Nia had lots of free time. One day, she decided to pass the time by building a very, *very* long line of dominoes.

A typical domino has dimensions , but some of Nia's dominoes are broken, and they have dimensions .

Nia wants to make a line of dominoes with dimensions . Nia has types of dominoes and types of dominoes. For each type of domino, Nia has an unlimited amount at her disposal. Dominoes need to have a fixed orientation in order to connect together in the line, so they cannot be rotated. Now Nia wonders how many possible ways she can make an line of dominoes using and dominoes. Two ways are considered different if they do not have the same number of dominoes or the domino in one way is of a different length or type than the domino in the other way (counting from the beginning, for any ).

Since this number may be large, please compute it modulo .

#### Input Specification

The first line of input will have , , and .

The second line of input will have .

**Warning:** The input is extremely large (up to 100MB). Please be careful with input methods (i.e. use the fastest possible input method your language supports). Take special note that the memory limit for this problem is 32MB. It is **not** guaranteed that a language slower than C/C++ can score full marks.

#### Output Specification

Output the answer on a single line.

#### Constraints

For all subtasks:

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

#### Sample Input 1

```
1 1 101
9
```

#### Sample Output 1

`55`

#### Sample Input 2

```
0 1 101
1337
```

#### Sample Output 2

`0`

#### Sample Input 3

```
1 0 101
2015
```

#### Sample Output 3

`1`

#### Sample Input 4

```
2 0 10007
1234567890
```

#### Sample Output 4

`9823`

#### Sample Input 5

```
123 456 787
88888888
```

#### Sample Output 5

`543`

#### Sample Input 6

```
956 381 10009
705923593712956959302756329278756282035756528101747656392654937104729
```

#### Sample Output 6

`5681`

In the spirit of Tengen Toppa Gurren Lagann, we have ramped up the test data to 11 for this problem.

## Comments

is there any way to get AC on this problem? reading 100 MB seems too much...

Reading 100MB is fine if you use getchar(). The time limit is 4.5s.

thanks, got ac using getchar()

Hi bossu, may I please inquire

Thanks,

bobhob314

`swaglordof80085`

Edit 2:By the way,## Write the

Contest on [2015-0]`Special Day`

4-20at 3:30 PM!