C - Multiple Sequences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N , M が与えられます。 長さ N の整数列 A であって、以下の条件を満たすものの数を答えてください。

  • 1 \leq A_i \leq M \left(i = 1, 2, \ldots, N\right)
  • A_{i+1} は A_i の倍数 \left(i = 1, 2, \ldots, N - 1\right)

ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを答えてください。

制約

  • 入力は全て整数
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5

入力

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

N M

出力

答えを出力せよ。

入力例 1

3 4

出力例 1

13

条件を満たす数列 A として、例えば以下のようなものが考えられます。

  • A = \left(1, 1, 4\right)
  • A = \left(3, 3, 3\right)
  • A = \left(1, 2, 4\right)

入力例 2

20 30

出力例 2

71166

入力例 3

200000 200000

出力例 3

835917264

Score : 500 points

Problem Statement

Given are integers N and M. How many sequences A of N integers satisfy the following conditions?

  • 1 \leq A_i \leq M \left(i = 1, 2, \ldots, N\right)
  • A_{i+1} is a multiple of A_i. \left(i = 1, 2, \ldots, N - 1\right)

Since the answer can be enormous, report it modulo 998244353.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5

Input

Input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

3 4

Sample Output 1

13

Some of the sequences A satisfying the conditions follow:

  • A = \left(1, 1, 4\right)
  • A = \left(3, 3, 3\right)
  • A = \left(1, 2, 4\right)

Sample Input 2

20 30

Sample Output 2

71166

Sample Input 3

200000 200000

Sample Output 3

835917264