#P6935. 我永远喜欢
我永远喜欢
题目描述
有 类樱花,第 类有 朵。同类樱花不可区分。考虑将全部樱花排成序列的每一种不同结果。
对一个序列,把首尾相接以确定相邻关系,然后按类别划分成极长连续段。同一段内的樱花类别相同,相邻两段的类别不同。若一段的长度为 ,它对快乐值的贡献为 。该序列的快乐值等于所有段的贡献之积。
求所有不同序列的快乐值之和对 取模的结果。不同序列仍分别计入,即使它们首尾相接后可以通过旋转互相得到。模意义下的除法使用乘法逆元。
输入格式
第一行一个整数 。
第二行 个正整数 。
输出格式
输出一行一个整数,表示所求的快乐值总和对 取模的结果。
样例
2
2 2
3
共有 种序列。 的快乐值均为 , 的快乐值均为 ,总和为 。
6
7 8 9 10 11 12
526836707
数据范围
本站评测中,,且 。原 PDF 中给出的类别数上限为 。原题时间限制 3 秒,内存限制 512 MB。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 15 | |
| 2 | , | |
| 3 | 20 | , |
| 4 | ||
| 5 | 30 | 无 |