#P7226. [2023省队模拟]序列

    ID: 7060 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-笛卡尔树双射计数格路计数反射原理阶乘逆元预处理

[2023省队模拟]序列

题目描述

一个长度为 nn 的序列是合法的,当且仅当它的元素均为 11 到 mm 的整数,且每个整数 1,2,…,m1,2,\ldots,m 至少出现一次。下标从 11 开始。

如果对每个区间 [i,j][i,j](1≤i≤j≤n1\le i\le j\le n),两个序列在该区间内取得最大值的最大下标都相同,则这两个序列不可区分。两个序列在该下标处的值可以不同。

求合法序列按上述不可区分关系划分所得的等价类数,对 998244353998244353 取模。

输入格式

一行两个正整数 n,mn,m。

输出格式

一行一个整数,表示答案。

样例输入 1

3 2

样例输出 1

4

样例输入 2

12345 12344

样例输出 2

86532350

样例输入 3

100000 123

样例输出 3

504776856

数据范围与约定

子任务 数据范围 分值
1 n,m≤8n,m\le8 10
2 n,m≤100000n,m\le100000,n−1≤mn-1\le m
3 n,m≤300n,m\le300 30
4 n,m≤2000n,m\le2000 20
5 n,m≤100000n,m\le100000 30