# [集训队互测 2023] 基础寄术练习题

## 题目描述

对于长度为 $n$ 的序列 $a$，定义 $f(a)=\dfrac{1}{\prod\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\{a_n\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\le k\le 2$**。

考虑所有满足以下三个条件的序列 $a$：

- $a$ 的长度为 $n$。
- $\forall i,j$，$a_i\ne a_j$。
- $1\le a_i\le m$。

求它们的 $f(a)$ 之和，答案对 $p$ 取模。保证 $p$ 是一个质数。

## 输入格式

第一行三个整数 $n,m,k,p$，分别代表序列长度，序列元素的上界和模数。

## 输出格式

一行一个整数表示答案对 $p$ 取模后的结果。

## 样例 #1

### 样例输入 #1

```
2 3 2 1000000007
```

### 样例输出 #1

```
966666675
```

## 样例 #2

### 样例输入 #2

```
3 5 2 998244353
```

### 样例输出 #2

```
148276980
```

## 样例 #3

### 样例输入 #3

```
6 10 2 1004535809
```

### 样例输出 #3

```
622165218
```

## 样例 #4

### 样例输入 #4

```
15 20 2 1064822107
```

### 样例输出 #4

```
53789887
```

## 样例 #5

### 样例输入 #5

```
30 40 1 265371653
```

### 样例输出 #5

```
179937201
```

## 提示

对于所有数据，保证 $2\le n\le m\le 100$，$10^8<p<1.07\times 10^9$ 且 $p$ 为质数，$1\le k\le 2$。

- Subtask 1 (10 pts)：$m\le 20$。
- Subtask 2 (25 pts)：$k=1$。
- Subtask 3 (15 pts)：$n=m\le 30$。
- Subtask 4 (10 pts)：$m\le 30$。
- Subtask 5 (15 pts)：$m\le 40$。
- Subtask 6 (10 pts)：$m\le 70$。
- Subtask 7 (15 pts)：$m\le 100$。