Score : $2000$ points
For each of the $K^{NM}$ ways to write an integer between $1$ and $K$ (inclusive) in every square in a square grid with $N$ rows and $M$ columns, find the value defined below, then compute the sum of all those $K^{NM}$ values, modulo $D$.
Input is given from Standard Input in the following format:
$N$ $M$ $K$ $D$
Print the sum of the $K^{NM}$ values, modulo $D$.
2 2 2 998244353
35
We have $1$ way to write integers such that the product of the $NM$ values is $16$, $4$ ways such that the product is $2$, and $11$ ways such that the product is $1$.
2 3 4 998244353
127090
31 41 59 998244353
827794103