Description

We call a sequence consisting only of $0,1$ an "alternating sequence" if and only if there are no adjacent $1$'s (adjacent $0$'s are allowed). For example, 000, 001, 101 are alternating sequences, while 110 is not.

For an alternating sequence of length $n$, let the counts of $0$ and $1$ be $x$ and $y$, respectively. Given parameters $a,b$, define the characteristic value of a sequence as $x^a y^b$. Note that any integer to the $0$-th power equals $1$ (including $0^0 = 1$).

Obviously there may be multiple alternating sequences of length $n$. We want to know the remainder modulo $m$ (where $m$ is a given prime) of the sum of characteristic values over all alternating sequences of length $n$.

For example, all alternating sequences of length $3$ are: 000, 001, 010, 100, 101. When $a = 1, b = 2$, we can compute: $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 Format

The input contains one line with four space-separated integers $n,a,b,m$.

Output Format

Output one line containing the result $\bmod m$.

3 1 2 1009

10

4 3 2 1009

204

Hint

For $30\%$ of the testdata, $1 \le n \le 15$.

For $100\%$ of the testdata, $1 \le n \le 10^7$, $1 \le a,b \le 45$, $10^7 \le m < 10^8$.

Translated by ChatGPT 5