← 返回题目列表

AtCoder · agc075_d

D. 最大产品加

中文机器翻译题面 查看原题

分数: 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