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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,m,k,y;
ll mod;
const int iu=1e6;
ll f[iu+1],inf[iu+1];
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
ll C(ll x,ll y){
	return f[x]*inf[y]%mod*inf[x-y]%mod;
}
int st[20];
int en[20];
int filled[1<<20];
ll dp[1<<20];
ll tab1(){
	for(int i=0; i<n ;i++){
		st[i]=i-k+1;
		en[i]=st[i]+m;
		st[i]=max(st[i],0);
	}
	for(int i=0; i<n ;i++) filled[1<<i]=en[i]-st[0];
	for(int i=1; i<(1<<n) ;i++){
		int id=__builtin_popcount(i);
		if(i!=(i&-i)) filled[i]=filled[i^(i&-i)]+filled[i&-i]+st[0]-st[id-1];
	}
	/*for(int i=0; i<(1<<n) ;i++) cout << filled[i] << ' ';
	cout << endl;*/
	dp[0]=1;
	for(int i=0; i<(1<<n)-1 ;i++){
		int id=__builtin_popcount(i);
		int sgn=1;
		for(int j=n-1; j>=0 ;j--){
			if((i>>j)&1){
				sgn=-sgn;
				continue;
			}
			ll ways;
			if(st[id]==0){
				ways=C(filled[i]+en[j]-1,en[j]-1);
			}
			else{
				ways=C(filled[i]+en[j]-st[id],en[j]-st[id]);
			}
			//cout << "trans " << i << ' ' << (i|(1<<j)) << ' ' << sgn << ' ' << ways << endl;
			if(sgn==-1) ways=(mod-ways);
			dp[i|(1<<j)]=(dp[i|(1<<j)]+dp[i]*ways)%mod;

		}
	}
	return dp[(1<<n)-1];
}
int g[25][50005],h[25][50005];
ll tab2(){
	int tot=0;
	ll res=1;
	for(int i=n; i>=1 ;i--){
		for(int j=m; j>=1 ;j--){
			if(i+j+k-1<=n+m){
				g[i][j]=g[i+1][j]+1;
				h[i][j]=h[i][j+1]+1;
				res=res*f[g[i][j]+h[i][j]-2]%mod*inf[g[i][j]+h[i][j]-1]%mod;
				++tot;
			}
		}
	}
	res=res*f[tot]%mod;
	y=tot;
	//cout << res << endl;
	return res;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m >> k >> mod;
	k=n+m-k;//1<=k<=n
	f[0]=1;
	for(int i=1; i<=iu ;i++) f[i]=f[i-1]*i%mod;
	inf[iu]=pw(f[iu],mod-2);
	for(int i=iu; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
	
	ll v1=tab1(),v2=tab2();
	cout << y << ' ';
	cout << v1*v2%mod << '\n';
}