QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8638. 排序

Statistics

题目描述

对于一个整数序列 $A=(a_1,a_2,...,a_n)$ ,考虑以下的递归过程:首先等概率地选取 $A$ 中一个值 $a_k$ ,将序列 $A$ 中所有小于 $a_k$ 的元素按照在 $A$ 中的位置依次排列为序列 $A_1$ ,将序列 $A$ 中所有大于 $a_k$ 的元素按照 $A$ 中的位置依次排列为序列 $A_2$ ,然后对于序列 $A_1、A_2$ 分别重复以上过程,直至序列为空时结束递归。一次递归的时间代价表示为过程中所有序列的长度和(包括最开始的序列) ,由于递归方式不确定,记 $T(A)$ 为对序列 $A$ 执行上述过程的期望时间代价。

现给定 $n,m$ ,请对于所有长度为 $n$ ,且满足 $1\le a_i \le m (i=1,2...n)$ 的整数序列 $A$ ,求出 $T(A)$ 的和。答案对 998244353 取模。

输入格式

从标准输入读入数据。

输入仅一行,两个正整数 $n,m$,分别表示序列的长度和元素的取值范围。

输出格式

输出到标准输出。

输出一行一个整数,表示 $T(A)$ 的和对 $998244353$ 取模的结果。

样例

输入

3 2

输出

32

样例

输入

5 4

输出

9236

样例

输入

25 15

输出

907094177

数据范围

对于 $20\%$ 的数据:$n,m \le 5$ 。

对于 $50\%$ 的数据:$n,m \le 30$ 。

对于另外 $20\%$ 的数据:$n \le 5, m \le 10^9$ 。

对于所有测试数据保证:$1\le n \le 100, 1\le m \le 10^9$ 。