分数: 1200 点
问题陈述
对于长度-N 正整数序列 A=(A_1,A_2,\dots,A_N),定义 f(A) 如下:
- 的最大值 A_iA_j + A_k 所有整数三元组 (i,j,k) 满意 1 \le i < j < k \le N.
求模数 998244353,长度-N 序列 A 的正整数,其间的所有元素 1 和 M,包含在内,这样 f(A) \le K.
约束
- 3 \le N \le 10^9
- 1 \le M,K \le 10^4
输入
输入由标准输入按以下格式给出:
N M K
输出
输出答案。
示例输入 1
3 5 4
示例输出 1
9
满足条件的序列是 (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(2,1,2),(1,3,1),(3,1,1),这是九个序列。
示例输入 2
4 5 7
示例输出 2
66
示例输入 3
123 456 789
示例输出 3
436486661
示例输入 4
1000000000 10000 10000
示例输出 4
855626126