Counting Mex‐Stable Sets

Given four integers k, n, p and M, consider the universe of integers \(U = \{0,1,2,\dots,2^{k}-1\}\). We wish to count the number of sets \(A_{0}\) satisfying the following conditions:

• Size and containment: \(A_{0}\) contains exactly n distinct integers from \(U\) and it must contain \(0\).
• MEX‐stability: The set \(A_{0}\) is mex‐stable, meaning that if \(m = \mex(A_{0})\) then all integers in \(\{0,1,2,\dots, m-1\}\) are contained in \(A_{0}\). (Note that by definition of \(\mex\), \(m \notin A_{0}\).)
• MEX‐limit: The mex–limit of \(A_{0}\) is defined to be \(\mex(A_{0})\), and it is given that \(\mex(A_{0}) = p\).

Thus, the above conditions force \(\{0,1,\dots, p-1\} \subseteq A_{0}\) and \(p \notin A_{0}\). In other words, if \(n < p\) then no such set exists. Otherwise, once \(\{0,1,\dots, p-1\}\) is fixed, the remaining n − p elements must be chosen from the set \(\{p+1, p+2, \dots,2^{k}-1\}\). Hence, the number of valid sets is given by

[ \text{Answer} = \begin{cases} 0, & \text{if } n < p \text{ or } 2^{k} - p - 1 < n - p,\[1mm] \binom{2^{k} - p - 1}{n - p} \pmod{M}, & \text{otherwise.} \end{cases} ]

Since the answer can be very large, output the result modulo \(M\). It is guaranteed that \(M-1\) is divisible by \(2^{18}\) (i.e. \(262144\)).

inputFormat

The input consists of a single line containing four space‐separated integers: k, n, p and M.

\(1 \leq k \leq \text{(small enough so that }2^{k}\text{ can be handled)}\), \(0 \leq p \leq n \leq 2^{k}\). You may assume that \(M\) is a prime number (or at least that the modular inverse exists for our computation) and that \(M-1\) is divisible by \(2^{18}\).

outputFormat

Output one integer: the number of valid sets \(A_{0}\) modulo \(M\).

sample

3 3 2 1000000007

5