Sum of Feature Values of Alternating Sequences

Consider a sequence consisting only of the digits \(0\) and \(1\). We call a sequence an alternating sequence if and only if it does not contain two consecutive \(1\)s (consecutive \(0\)s are allowed). For example, 000, 001, and 101 are alternating sequences, whereas 110 is not.

For an alternating sequence of length \(n\), let \(x\) and \(y\) be the number of occurrences of \(0\) and \(1\) respectively. Given parameters \(a\) and \(b\), the feature value of the sequence is defined as \[ x^a y^b, \] with the convention that any integer raised to the 0th power equals \(1\) (including \(0^0=1\)).

Since there might be multiple alternating sequences of length \(n\), compute the sum of the feature values for all such sequences, and output the result modulo a given prime \(m\).

The key observation is that for a fixed number \(y\) of ones, the number of alternating sequences is given by the combinatorial formula \[ C(n-y+1, y), \] which counts the ways to place \(y\) ones in the \(n\)-length sequence so that no two are adjacent. Note that in such a sequence, the number of \(0\)s is \(x=n-y\). Thus, the answer is \[ \sum_{y=0}^{\lfloor\frac{n+1}{2}\rfloor} C(n-y+1,y)\cdot (n-y)^a\cdot y^b \pmod{m}. \]

inputFormat

The input consists of a single line containing four space‐separated integers \(n\), \(a\), \(b\) and \(m\), where \(m\) is a prime number.

outputFormat

Output a single integer representing the sum of the feature values of all alternating sequences of length \(n\), taken modulo \(m\).

sample

3 1 2 1000000007

10