Problem Description

We define a sequence consisting only of 0s and 1s as an "interleaved sequence" if and only if there are no adjacent 1s in the sequence (adjacent 0s are allowed). For example, 000, 001, and 101 are interleaved sequences, while 110 is not.

For an interleaved sequence of length \( n \), let \( x \) and \( y \) be the counts of 0s and 1s respectively. Given parameters \( a \) and \( b \), the characteristic value of an interleaved sequence is defined as \( x^a y^b \). Note that any integer raised to the power of 0 is considered to be 1 (including \( 0^0 = 1 \)).

Clearly, there can be multiple interleaved sequences of length \( n \). We want to know the sum of the characteristic values of all interleaved sequences of length \( n \), modulo \( m \) (where \( m \) is a given prime number).

For example, all interleaved sequences of length 3 are: 000, 001, 010, 100, 101. When \( a = 1 \) and \( 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 Format

The input file contains a single line with three integers \( n \), \( a \), \( b \), and \( m \) separated by spaces.

Output Format

The output file contains a single line with the result of the calculation.

Sample Input and Output

Sample Input #1

3 1 2 1009

Sample Output #1

10

Sample Input #2

4 3 2 1009

Sample Output #2

204

Notes

For 30% of the data, \( 1 \leq n \leq 15 \).

For 100% of the data, \( 1 \leq n \leq 10000000 \), \( 0 \leq a, b \leq 45 \), \( m < 100000000 \).

见题面 Input 部分

见题面 Output 部分