We call a sequence consisting of $0$s and $1$s an "alternating sequence" if and only if there are no adjacent $1$s in the sequence (there may be adjacent $0$s). For example, $000$, $001$, and $101$ are alternating sequences, while $110$ is not.
For an alternating sequence of length $n$, let $x$ and $y$ be the number of $0$s and $1$s in it, respectively. Given parameters $a$ and $b$, the characteristic value of an alternating sequence is defined as $x^a y^b$. Note that any integer to the power of $0$ equals $1$ (including $0^0=1$).
Obviously, there are many alternating sequences of length $n$. We want to know the sum of the characteristic values of all alternating sequences of length $n$, modulo $m$ ($m$ is a given prime number).
For example, all alternating sequences of length $3$ are: $000$, $001$, $010$, $100$, $101$. When $a=1, b=2$, we can calculate: $3^1 \times 0^2 + 2^1 \times 1^2 + 2^1 \times 1^2 + 2^1 \times 1^2 + 1^1 \times 2^2 = 10$.
Input
The input consists of a single line containing four space-separated integers $n$, $a$, $b$, and $m$.
Output
Output a single line containing the result of the calculation.
Examples
Input 1
3 1 2 1009
Output 1
10
Input 2
4 3 2 1009
Output 2
204
Constraints
- For $30\%$ of the data, $1 \le n \le 15$.
- For $100\%$ of the data, $1 \le n \le 10000000$, $0 \le a, b \le 45$, $m < 100000000$.