#1946. count

    ID: 1946 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2398来源:qoj.ac数据:公开样例数学

count

count

题目描述

标题: count - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

如果一个序列满足序列长度为n,序列中的每个数都是1到m内的整数,且所有1到m内的整数都在序列中出现过,则称这是一个挺好序列。

对于一个序列A,记fA(l,r)为A的第l个到第r个数中最大值的下标(如果有多个最大值,取下标最小的)。

两个序列A和B同构,当且仅当A和B长度相等,且对于任意i≤j,均有fA(i,j)=fB(i,j)。

给出n,m,求有多少种不同构的挺好序列。答案对998244353取模。

输入格式

一行两个正整数n,m。

输出格式

一行一个整数,表示有多少种不同构的挺好序列。

样例一

input

3 2

output

4

explanation

一共6种挺好序列:2 1 1,1 2 1,1 1 2,1 2 2,2 1 2,2 2 1。其中2 1 1和2 2 1同构,1 2 1和1 2 2同构,所以一共有4种不同构的挺好序列。

样例二

input

8 5

output

1341

样例三

input

100000 99999

output

944488805

样例四

input

300 200

output

430256456

样例五

input

2000 1000

output

267823945

样例六

input

100000 50000

output

779381353

限制与约定

子任务 n,m≤ 特殊性质 分值 1 8 10 2 100000 m≥n−1 10 3 300 30 4 2000 20 5 100000 30

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
4

样例 2

8 5
1341