题目描述
有 n 个小朋友正在玩传球游戏。一开始(第 0 分钟)有 k 个球,开始时编号为 i 的球在小朋友 pi 的手里。
接下来手上有球的小朋友可以决定自己手里每个球下一分钟传给谁。注意同一个小朋友手上的球可以有不同的去向。
为了缩小每个人的持球时间的差距,规定上一分钟拿球的小朋友这一分钟不能拿球。同时为了缩小每个人持球数量的差距,规定拿球最多的小朋友不能拿超过 ⌊0.5k⌋ 个球(⌊x⌋ 表示不超过 x 的最大整数)。
你需要计算前 t 分钟有多少种传球方法。两种传球方法不同,当且仅当存在 (b,i),第 b 个球第 i 分钟在不同的人手里。
输入格式
输入的第一行有三个整数 n,k,t,表示小朋友数、球数和游戏分钟数。
第二行有 k 个整数 p1,p2,…,pk 表示每个球在哪个小朋友手上。
输出格式
输出仅包含一行一个整数 ans,表示方案数。
由于输出可能过大,你需要对质数 109+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×(36+144+24)=1224。
【数据范围】
测试点编号 |
n≤ |
k≤ |
t≤ |
1 |
5 |
4 |
=3 |
2∼3 |
=5 |
100 |
100 |
4∼6 |
106 |
7∼8 |
=6 |
=99 |
100 |
9∼10 |
106 |
11∼12 |
107 |
100 |
1 |
13∼14 |
3 |
106 |
15∼17 |
100 |
100 |
18∼20 |
106 |
对于全部数据,保证 4≤n≤107,2≤k≤100,1≤t≤106。
题目保证初始状态合法。