#arc116c. [arc116_c]Multiple Sequences

[arc116_c]Multiple Sequences

题目描述

给定整数NNMM,求满足以下条件的长度为NN的整数序列AA的数量:

  • 1AiM(i=1,2,,N)1 \leq A_i \leq M \quad (i = 1, 2, \ldots, N)
  • Ai+1A_{i+1}AiA_i的倍数 (i=1,2,,N1)\quad (i = 1, 2, \ldots, N - 1)

由于答案可能非常大,要对998244353998244353取模。

约束条件

  • 输入中的所有值均为整数。
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1M2×1051 \leq M \leq 2 \times 10^5

输入

输入以以下格式从标准输入给出:

NN MM

输出

输出答案。


示例输入1

3 4

示例输出1

13

满足条件的一些序列AA如下:

  • A=(1,1,4)A = (1, 1, 4)
  • A=(3,3,3)A = (3, 3, 3)
  • A=(1,2,4)A = (1, 2, 4)

示例输入2

20 30

示例输出2

71166

示例输入3

200000 200000

示例输出3

835917264