Buying Stamps

A post office sells $N$ kinds of stamps that cost 1 won each and $M$ kinds that cost 2 won each. Stamps of different kinds count as different stamps.

Write a program that counts the ways to buy exactly $K$ won worth of stamps and prints that count modulo $P$.

You may buy several copies of the same kind, and the post office has an unlimited supply. The order of purchase does not matter, so two ways are the same when they take the same number of stamps of every kind. The whole $K$ won must be spent exactly, with nothing left over.

The first line contains $N$, $M$, $K$, and $P$, separated by spaces. ($0 \le N, M \le 300$, $1 \le K \le 10^{12}$, $3 \le P \le 1{,}000{,}000$, and $P$ is prime.)

Print the number of ways to buy the stamps, modulo $P$, on the first line.