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