#P12735. 回报
回报
题目背景
在我看来,得到太多的人明明是我,反倒是我该思考怎么回报才对。
——浅村悠太
题目描述
悠太需要帮沙季找到合适的学习用音乐。
他找到了一个包含 首音乐的专辑,其中的音乐编号为从 至 ,播放每首音乐均需要 分钟。沙季有 A 和 B 两门需要学的课程,每次学习 A 和 B 分别需要花 分钟。为了更好地帮助她,悠太打算将音乐的播放顺序重新排列。具体地,他要选择一个长为 的排列 ,使得其中存在两个长度分别为 的循环 ,且 中的任意一个元素小于 中的任意一个元素。
排列中的一个长为 的循环 是一个由不同整数组成的序列 ,满足 ,,且 。
悠太想要求出有多少满足要求的排列 。由于答案可能很大,你只需要告诉他答案对 取模的结果。
输入格式
输入一行三个整数表示序列长度 与 。
输出格式
输出一行一个整数,表示满足要求的排列的数量取模 的结果。
4 2 1
3
678 12 34
951781526
1987 654 321
27905503
1000000 13 20
912829543
提示
样例 1 解释
满足要求的排列有 ,共 个。
数据范围与限制
本题采用捆绑测试,各 Subtask 的限制与分值如下。
Subtask No. | 特殊性质 | 分值 | 依赖子任务 | |
---|---|---|---|---|
有 | ||||
无 | ||||
有 | ||||
无 | ||||
有 | ||||
无 |
特殊性质:。
对于所有数据,,。