Problem: 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.

* For each of the NM squares, find the minimum among the N+M-1 integers written in the square's row or the square's column. The value defined for the grid is the product of all these NM values.

Constraints

* 1 \leq N,M,K \leq 100
* 10^8 \leq D \leq 10^9
* N,M,K, and D are integers.
* D is prime.

Input

Input is given from Standard Input in the following format:


N M K D


Output

Print the sum of the K^{NM} values, modulo D.

Examples

Input

2 2 2 998244353


Output

35


Input

2 3 4 998244353


Output

127090


Input

31 41 59 998244353


Output

827794103

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;
int mod;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); }
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }
inline int fpow( int b , int k ) {
  int res = 1;
  while( k ) {
    if( k & 1 ) res = 1LL * res * b % mod;
    b = 1LL * b * b % mod; k >>= 1;
  }
  return res;
}

int coe[N][N][N][2] , f[N][N][N][2] , n , m , k , binom[N][N];

int main( void ) {
  cin >> n >> m >> k >> mod;
  for( int i = 0 ; i < N ; ++i ) {
    binom[i][0] = 1;
    for( int j = 1 ; j <= i ; ++j )
      binom[i][j] = pls( binom[i - 1][j] , binom[i - 1][j - 1] );
  }
  f[0][0][0][0] = 1;
  for( int v = 0 , tmp ; v < k ; ++v )
    for( int j = 0 ; j <= m ; ++j ) {
      tmp = 1LL * mns( fpow( v + 1 , m - j ) , fpow( v , m - j ) ) * fpow( k - v , j ) % mod;
      coe[v][0][j][0] = 1;
      for( int i = 1 ; i <= n ; ++i )
        coe[v][i][j][0] = 1LL * coe[v][i - 1][j][0] * tmp % mod;
    }
  for( int v = 0 , tmp ; v < k ; ++v )
    for( int i = 0 ; i <= n ; ++i ) {
      tmp = 1LL * mns( fpow( k - v , i ) , fpow( k - v - 1 , i ) ) * fpow( v + 1 , n - i ) % mod;
      coe[v][i][0][1] = 1;
      for( int j = 1 ; j <= m ; ++j )
        coe[v][i][j][1] = 1LL * coe[v][i][j - 1][1] * tmp % mod;
    }
  for( int v = 0 , foo ; v < k ; ++v )
    for( int i = 0 ; i <= n ; ++i )
      for( int j = 0 ; j <= m ; ++j ) {
        if( f[v][i][j][0] ) {
          foo = f[v][i][j][0];
          for( int l = 0 ; l + i <= n ; ++l ) 
            inc( f[v][i + l][j][1] , 1LL * foo * coe[v][l][j][0] % mod * binom[n - i][l] % mod );
        }
        if( f[v][i][j][1] ) {
          foo = f[v][i][j][1];
          for( int l = 0 ; l + j <= m ; ++l ) 
            inc( f[v + 1][i][j + l][0] , 1LL * foo * coe[v][i][l][1] % mod * binom[m - j][l] % mod );
        }
      }
  cout << f[k][n][m][0];
  return 0;
}