对于长度为 n 的序列 a,定义 f(a)=1n∏i=ksi,其中 si 为 {an} 的前缀和数组,k 是给定的常数且 1≤k≤2。
考虑所有满足以下三个条件的序列 a:
- a 的长度为 n。
- ∀i,j,ai≠aj。
- 1≤ai≤m。
求它们的 f(a) 之和,答案对 p 取模。保证 p 是一个质数。
输入格式
第一行三个整数 n,m,k,p,分别代表序列长度,序列元素的上界和模数。
输出格式
一行一个整数表示答案对 p 取模后的结果。
样例
输入样例 1
2 3 2 1000000007
输出样例 1
966666675
输入样例 2
3 5 2 998244353
输出样例 2
148276980
输入样例 3
6 10 2 1004535809
输出样例 3
622165218
输入样例 4
30 40 1 265371653
输出样例 4
179937201
限制与约定
对于所有数据,保证 2≤n≤m≤100,108<p<1.07×109 且 p 为质数,1≤k≤2。
- Subtask 1 (10 pts):m≤20。
- Subtask 2 (25 pts):k=1。
- Subtask 3 (15 pts):n=m≤30。
- Subtask 4 (10 pts):m≤30。
- Subtask 5 (15 pts):m≤40。
- Subtask 6 (10 pts):m≤70。
- Subtask 7 (15 pts):m≤100。
时间限制:2s。
空间限制:512MB。