对于一个正整数 $\alpha$，考虑以下长度为 $\alpha n$ 的序列 $a_1, a_2, \dots, a_{\alpha n}$，其满足：

• 对于每个 $1 \le k \le n$，该序列恰好包含 $\alpha$ 个 $k$。
• 如果存在两个整数 $i < j$ 使得 $a_i = a_j$，则对于任何 $i < k < j$，都有 $a_k \ge a_i$。

我们称满足上述要求的序列为 $(n, \alpha)$-序排列。

现在，给定一个 $(n_0, \alpha)$-序排列 $P = p_1, p_2, \dots, p_{\alpha n_0}$，以及两个整数 $n$ 和 $m$，请计算满足以下条件的 $(n, \alpha)$-序排列 $B = b_1, b_2, \dots, b_{\alpha n}$ 的数量：

• $P$ 是 $B$ 的子序列。
• 恰好有 $m$ 个下标 $i$ 满足 $1 \le i < \alpha n$ 且 $b_i > b_{i+1}$。

当且仅当可以通过从 $B$ 中删除某些元素（可能不删除或全部删除）得到 $P$ 时，我们称 $P$ 是 $B$ 的子序列。

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含四个整数 $\alpha, n, m, n_0$ ($1 \le n \le 10, 0 \le m < n, 1 \le n_0 \le n, 1 \le \alpha n \le 10$)。

第二行包含 $\alpha n_0$ 个正整数 $p_1, p_2, \dots, p_{\alpha n_0}$ ($1 \le p_i \le n_0$)，表示给定的序列 $P$。保证 $P$ 构成一个 $(n_0, \alpha)$-序排列。

输出格式

输出一行，包含一个整数，表示满足要求的序列 $B$ 的数量。

样例

样例输入 1

1 4 2 2
2 1

样例输出 1

7

样例输入 2

2 4 2 2
1 2 2 1

样例输出 2

19