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 ~2 \times 1~, but some of Nia's dominoes are broken, and they have dimensions ~1 \times 1~.

Nia wants to make a line of dominoes with dimensions ~N \times 1~. Nia has ~A~ types of ~1 \times 1~ dominoes and ~B~ types of ~2 \times 1~ 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 ~N \times 1~ line of dominoes using ~2 \times 1~ and ~1 \times 1~ dominoes. Two ways are considered different if they do not have the same number of dominoes or the ~i^{th}~ domino in one way is of a different length or type than the ~i^{th}~ domino in the other way (counting from the beginning, for any ~i~).

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

Input Specification

The first line of input will have ~A~, ~B~, and ~M~.

The second line of input will have ~N~.

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:

~0 \le A, B < M \le 10\,009~

~M > 100~

Subtask 1 [10%]

~1 \le N \le 100\,000~

Subtask 2 [30%]

~1 \le N \le 10^9~

Subtask 3 [60%]

~1 \le N \le 10^{(10^8)}~

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.