题目描述

有 $n$ 个小朋友正在玩传球游戏。一开始（第 $0$ 分钟）有 $k$ 个球，开始时编号为 $i$ 的球在小朋友 $p_i$ 的手里。

接下来手上有球的小朋友可以决定自己手里每个球下一分钟传给谁。注意同一个小朋友手上的球可以有不同的去向。

为了缩小每个人的持球时间的差距，规定上一分钟拿球的小朋友这一分钟不能拿球。同时为了缩小每个人持球数量的差距，规定拿球最多的小朋友不能拿超过 $\lfloor 0.5k\rfloor$ 个球（$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数）。

你需要计算前 $t$ 分钟有多少种传球方法。两种传球方法不同，当且仅当存在 $(b,i)$，第 $b$ 个球第 $i$ 分钟在不同的人手里。

输入格式

输入的第一行有三个整数 $n,k,t$，表示小朋友数、球数和游戏分钟数。

第二行有 $k$ 个整数 $p_1,p_2,\ldots,p_k$ 表示每个球在哪个小朋友手上。

输出格式

输出仅包含一行一个整数 $ans$，表示方案数。

由于输出可能过大，你需要对质数 $10^9+7$ 取余。

样例 #1

样例输入 #1

6 4 2
1 2 3 4

样例输出 #1

1224

提示

【样例解释】

第 $1$ 分钟，只有两个小朋友上一分钟没拿到球，每人又不能拿超过 $2$ 个球，因此每人恰好拿 $2$ 个球，共有 $6$ 种传法。

第 $2$ 分钟，有 $4$ 个小朋友可以接球，考虑 $4$ 的拆分：

• $2+2$，拿球的小朋友有 $6$ 种组合，每种组合贡献 $6$ 种传球方式，共 $36$ 种传球方式。
• $2+1+1$，有 $144$ 种传球方式。
• $1+1+1+1$，有 $24$ 种传球方式。

因此总答案为 $6\times (36+144+24)=1224$。

【数据范围】

对于全部数据，保证 $4\le n\le 10^7$，$2\le k\le 100$，$1\le t\le 10^6$。

题目保证初始状态合法。