#P18256. Ma Meilleure Ennemie

Ma Meilleure Ennemie

Ma Meilleure Ennemie

“我们能不能假装,这是第一次?”

Ekko 刚刚发明了能够回到过去的 Z-Drive。Heimerdinger 原本想用它把 Ekko 送回正确的宇宙,但异常现象造成了时空扭曲,使得 nn 个 Ekko 来到了同一个宇宙。

现在共有 mm 个宇宙,编号为 1,2,…,m1,2,\ldots,m。Heimerdinger 使用以下方法决定把每个 Ekko 送到哪个宇宙:

  1. 将 Ekko 编号为 0,1,…,n−10,1,\ldots,n-1,并划分成若干组。最初,所有 Ekko 都在同一组中。
  2. 选择一个尚未送走的组进行处理。
  3. 从 [1,m][1,m] 中选择一个好整数 xx。这里,xx 是好整数,当且仅当对当前组内的每个 Ekko ii,编号为 (i+x) mod n(i+x)\bmod n 的 Ekko 也在这一组中。
    例如,当 n=4n=4、当前组为 {0,2}\{0,2\} 时,x=3x=3 不是好整数,而 x=2x=2 和 x=4x=4 都是好整数。
  4. 把当前组划分成若干个临时组,使得每个临时组内的任意 Ekko ii 与 (i+x) mod n(i+x)\bmod n 都属于同一个临时组。在所有满足条件的划分中,选择临时组数量最多的划分。
    例如,当 n=4n=4、当前组为 {0,1,2,3}\{0,1,2,3\}、x=2x=2 时,会划分成 {0,2}\{0,2\} 和 {1,3}\{1,3\}。
  5. 如果只得到一个临时组,就把该组所有 Ekko 送到宇宙 xx;否则,这些临时组分别成为新的组,继续按照上述方法处理。

虽然这个方法可能把多个 Ekko 送往同一个宇宙,但现在已无暇修正。

给定 n,mn,m,求这种方法能够产生多少种不同的最终结果。两种结果不同,当且仅当至少一名 Ekko 最终被送到的宇宙编号不同。

答案对 998244353998244353 取模。

输入格式

输入一行两个整数 n,mn,m,分别表示 Ekko 的数量和宇宙的数量。

输出格式

输出一行一个整数,表示不同最终结果的数量,对 998244353998244353 取模。

数据范围

1≤n,m≤1018.1\le n,m\le10^{18}.

输入只有一组数据。分组时编号始终按最初的模 nn 编号解释;各组可以分别选择不同的好整数。

样例 1

4 4
6

样例 2

2338 1470
18530141