Buying Stamps

The post office sells stamps. There are $N$ kinds of stamps priced at 1 won and $M$ kinds priced at 2 won.

Write a program that counts the ways to buy stamps worth exactly $K$ won.

You may buy several stamps of the same kind. The post office has an unlimited number of each stamp. You must use exactly $K$ won.

The first line contains $N$, $M$, $K$, and $P$. ($0 \le N, M \le 1000$, $1 \le K \le 1000$, $3 \le P \le 1{,}000{,}000$, $P$ is prime.)

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