1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef long double db;
mt19937 mrand(1111); 
ll mod;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010000;
ll fac[N],fnv[N];
int a,b,c;
ll f(int n,int m) {
	ll ans=fac[n*m];
	rep(i,0,m) ans=ans*fac[i]%mod;
	rep(i,0,n) ans=ans*fac[i]%mod;
	rep(i,0,n+m) ans=ans*fnv[i]%mod;
	return ans;
}
ll f(vector<int> l) {
	int s=0;
	for (auto x:l) s+=x;
	ll ans=fac[s];
	rep(i,0,SZ(l)) l[i]=l[i]+SZ(l)-i-1;
	for (auto x:l) ans=ans*fnv[x]%mod;
	rep(i,0,SZ(l)) rep(j,i+1,SZ(l)) ans=ans*(l[i]-l[j])%mod;
	return ans;
}
ll g(vector<int> l) {
	int s=0;
	for (auto x:l) s+=x;
	ll ans=fac[s];
	for (auto x:l) ans=ans*fnv[x]%mod;
	ll p=1,q=1;
	rep(i,0,SZ(l)) rep(j,i+1,SZ(l)) {
		p=p*(l[i]-l[j])%mod;
		q=q*(l[i]+l[j])%mod;
	}
	ans=ans*p%mod*powmod(q,mod-2)%mod;
	return ans;
}
ll binom(int a,int b) {
	if (b<0||b>a) return 0;
	return fac[a]*fnv[b]%mod*fnv[a-b]%mod;
}
ll E(int r,int p,int s) {
	if (r%2==0) {
		ll ans=1;
		for (int l=r+1;l<2*p-r+2;l++) 
			ans=ans*powmod(l+2*s,r/2)%mod;
		for (int l=2;l<=r;l++) {
			ans=ans*powmod((l+2*s)*(2*p-l+2*s+2),l/2)%mod;
		}
		ans=powmod(ans,mod-2);
		return ans;
	} else {
		ll ans=E(r-1,p,s);
		ans=ans*fac[(r-1)/2+s]%mod*fnv[p-(r-1)/2+s]%mod;
		return ans;
	}
}
ll truncated(int m,int n,int k) {
	if (k==0) return f(m,n);
	assert(m>=n&&n>k);
	ll ans=binom(n*m-k*(k+1)/2,m*(n-k-1))*f(n-k-1,m)%mod;
	VI l;
	rep(i,0,k+1) l.pb(m-i);
	ans=ans*g(l)%mod;
	ans=ans*E(k+1,m,n-k-1)%mod*powmod(E(k+1,m,0),mod-2)%mod;
	return ans;
}

int main() {
	scanf("%d%d%d%lld",&a,&b,&c,&mod);
	fac[0]=fnv[0]=1;
	rep(i,1,a*b+100) {
		fac[i]=fac[i-1]*i%mod;
		fnv[i]=powmod(fac[i],mod-2);
	}
	int k=a+b-1-c;
	int ans=a*b-k*(k+1)/2;
	VI r;
	rep(i,0,a) r.pb(b-max(k-i,0));
	reverse(all(r));
	ll ans2=truncated(b,a,k)*f(r)%mod;
	printf("%d %lld\n",ans,ans2);
}