分数: 500 点
问题陈述
正在进行整数序列展览,其中整数序列聚集在一处并进行评估。这里,每个长度的整数序列 N 由之间的整数组成 1 和 K (含)被评估并给出一个整数分数 1 和 M (含)。
打印数字,模数 998244353,为每个评估序列提供评分的方法 1 和 M.
这里,当存在评估序列时,两种方式被认为是不同的 A = (A_1, A_2, \ldots, A_N) 即两种方式给出的分数不同。
约束
- 1 \leq N, K, M \leq 10^{18}
- N, K,和 M 是整数。
输入
输入由标准输入按以下格式给出:
N K M
输出
打印数字,模数 998244353,为每个评估序列提供评分的方法 1 和 M.
示例输入 1
2 2 2
示例输出 1
16
评估四个序列: (1, 1), (1, 2), (2, 1),和 (2, 2)。有 16 给每个序列打分的方法 1 和 2,如下。
- 给 1 to (1, 1), 1 to (1, 2), 1 to (2, 1),和 1 to (2, 2)
- 给 1 to (1, 1), 1 to (1, 2), 1 to (2, 1),和 2 to (2, 2)
- 给 1 to (1, 1), 1 to (1, 2), 2 to (2, 1),和 1 to (2, 2)
- 给 1 to (1, 1), 1 to (1, 2), 2 to (2, 1),和 2 to (2, 2)
- \cdots
- 给 2 to (1, 1), 2 to (1, 2), 2 to (2, 1),和 2 to (2, 2)
因此,我们打印 16.
示例输入 2
3 14 15926535
示例输出 2
109718301
请务必打印模数计数 998244353.