G - Divisible by 3 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 650 点

問題文

正整数 n の正の約数の総和が 3 で割り切れる時、n を良い整数と呼びます。
正整数 N, M が与えられます。長さ M の正整数列 A のうち、 A の要素の総積が N 以下の良い整数になるものの個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^{10}
  • 1 \leq M \leq 10^5
  • N, M は整数

入力

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

N M

出力

答えを出力せよ。

入力例 1

10 1

出力例 1

5

条件を満たす数列は次の 5 個です。

  • (2)
  • (5)
  • (6)
  • (8)
  • (10)

入力例 2

4 2

出力例 2

2

条件を満たす数列は次の 2 個です。

  • (1, 2)
  • (2, 1)

入力例 3

370 907

出力例 3

221764640

入力例 4

10000000000 100000

出力例 4

447456146

Score : 650 points

Problem Statement

We call a positive integer n a good integer if and only if the sum of its positive divisors is divisible by 3.
You are given two positive integers N and M. Find the number, modulo 998244353, of length-M sequences A of positive integers such that the product of the elements in A is a good integer not exceeding N.

Constraints

  • 1 \leq N \leq 10^{10}
  • 1 \leq M \leq 10^5
  • N and M are integers.

Input

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

N M

Output

Print the answer.

Sample Input 1

10 1

Sample Output 1

5

There are five sequences that satisfy the conditions:

  • (2)
  • (5)
  • (6)
  • (8)
  • (10)

Sample Input 2

4 2

Sample Output 2

2

There are two sequences that satisfy the conditions:

  • (1, 2)
  • (2, 1)

Sample Input 3

370 907

Sample Output 3

221764640

Sample Input 4

10000000000 100000

Sample Output 4

447456146