P4456 [CQOI2018] Alternating Sequence

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$.

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

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

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