← 返回题目列表

AtCoder · abc228_e

H. 整数序列公平

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

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