#P18885. [2026多校联测]序列计数

[2026多校联测]序列计数

题目描述

我们称一个 整数 序列 a1,a2,⋯,ana_1,a_2,⋯,a_n​ 是好的,当且仅当:

  • 对所有 1≤i≤n1≤i≤n,都有 1≤ai≤m1≤a_i≤m。
  • 对任意 1≤i<n1≤i<n,以下两个条件中至少成立一个:
    • ai≤ai+1a_i≤a_{i+1}
    • (ai mod ai+1)>0(a_i \bmod a_{i+1})>0

现在给定 n,mn,m,请你求出好的序列 {an}\{a_n\} 共有多少个。由于这个数可能较大,你只需要求出其对 998,244,353998,244,353 取模后的结果。

输入格式

输入只有一行,包含两个正整数 n,mn,m。

输出格式

输出一行一个非负整数,表示答案。

输入输出样例

输入 #1

2 5

输出 #1

20

输入 #2

5 3

输出 #2

63

输入 #3

301 338

输出 #3

469841778

输入 #4

1389 1427

输出 #4

610078558

输入 #5

191809 183589

输出 #5

251353885

数据范围与约定

对于全部的数据,有 1≤n,m≤2×1051\leq n,m\leq 2\times 10^5。

本题采用 subtask 捆绑测试,无子任务依赖。

  • 子任务 1 (8分) :n,m≤8n,m\leq 8。

  • 子任务 2 (12分) :n,m≤500n,m\leq 500。

  • 子任务 3 (25分) :n,m≤2000n,m\leq 2000。

  • 子任务 4 (25分) :n,m≤5×104n,m\leq 5\times 10^4。

  • 子任务 5 (30分) :无特殊限制。