Product of Binomial Subset Counts Modulo p

Consider two positive integers (n) and (m) that are coprime, and an integer (k). Define the function (F(n,m,k)) as the number of (m)-element subsets (S) of the set ({1,2,\ldots,n+m-1}) satisfying [ \sum_{x\in S} x \equiv k \pmod{n}, ] that is, (F(n,m,k)) counts the number of (m)-element subsets whose elements sum to a number congruent to (k) modulo (n).

It can be shown that when (\gcd(n,m)=1) the subsets are uniformly distributed among residue classes modulo (n). Hence, for any (k), we have [ F(n,m,k)=\frac{1}{n}\binom{n+m-1}{m}. ]

Given positive integers (N, M, K) and a prime (p), you are required to compute the product [ \prod_{\substack{1\le i\le N,,1\le j\le M\ \gcd(i,j)=1}} ;\prod_{x=1}^{K} F(i,j,x) \pmod{p}. ] Since for fixed (i) and (j) the function (F(i,j,x)) is independent of (x), the inner product is simply (F(i,j,x)^K) (with any (x)). Therefore, the task is equivalent to computing [ \prod_{\substack{1\le i\le N,,1\le j\le M\ \gcd(i,j)=1}} \Biggl(\frac{1}{i}\binom{i+j-1}{j}\Biggr)^K \pmod{p}. ]

Note: Beware of constant factors in your implementation. Efficient computation of binomial coefficients modulo (p) and modular inverses is required.

inputFormat

The input consists of a single line containing four space-separated positive integers:

• N \( (1 \le N) \)
• M \( (1 \le M) \)
• K \( (1 \le K) \)
• p (a prime number)

It is guaranteed that the input values are such that the answer can be computed efficiently.

outputFormat

Output a single integer, the value of the product described above, taken modulo p.

sample

2 2 1 1000000007

1