B - Product of Divisors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

A^{B} の正の約数の総積は A で最大何回割り切れますか。

制約から割り切れる回数が有限回であることが示せるので、その答えを 998244353 で割ったあまりを求めてください。

制約

  • 2\leq A\leq 10^{12}
  • 0\leq B\leq 10^{18}
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

A B

出力

答えを出力してください。

入力例 1

2 3

出力例 1

6

A^{B}=8 の正の約数は 1,2,4,8 で、その総積は 64 となります。 64 は 2 で 6 回割り切れるので、6 を出力します。

入力例 2

924 167

出力例 2

867046524

入力例 3

167167167167 0

出力例 3

0

Score : 500 points

Problem Statement

At most how many times can the product of all positive divisors of A^{B} be divided by A?

It can be shown from the constraints that this count is finite, so find it modulo 998244353.

Constraints

  • 2\leq A\leq 10^{12}
  • 0\leq B\leq 10^{18}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

A B

Output

Print the answer.

Sample Input 1

2 3

Sample Output 1

6

The positive divisors of A^{B}=8 are 1, 2, 4, and 8, whose product is 64. 64 can be divided by 2 at most six times, so print 6.

Sample Input 2

924 167

Sample Output 2

867046524

Sample Input 3

167167167167 0

Sample Output 3

0