#ARC116C. Multiple Sequences

    ID: 1610 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>普及+/提高−组合数学数论质因数分解

Multiple Sequences

Multiple Sequences

时间限制:2s
空间限制:1024MB

题目描述

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

  • 对所有 1≤i≤N1\le i\le N,都有 1≤Ai≤M1\le A_i\le M;
  • 对所有 1≤i<N1\le i<N,Ai+1A_{i+1} 是 AiA_i 的倍数。

答案可能很大,请输出其对 998244353998244353 取模的结果。

输入格式

一行两个整数 N,MN,M。

输出格式

输出一个整数,表示答案对 998244353998244353 取模的结果。

样例输入 1

3 4

样例输出 1

13

样例输入 2

20 30

样例输出 2

71166

样例输入 3

200000 200000

样例输出 3

835917264

数据范围

对于所有数据,1≤N,M≤2×1051\le N,M\le 2\times 10^5。

子任务编号 分值 特殊限制
1 10 N=1N=1
2 15 N≤8N\le 8,M≤50M\le 50
3 20 N,M≤2000N,M\le 2000
4 25 M≤5000M\le 5000
5 30 无特殊限制