题目背景

春生秋死，不知冬至。

题目描述

给你 $1 \sim k$ 的整数，你可以选其中的数，组成长度为 $n$ 的串（可重复使用），且不能有子串是 $1\sim k$ 的排列。

问方案总数模 $998244353$。

输入格式

一行两个正整数 $n,k$。

输出格式

一行一个整数，表示方案总数模 $998244353$ 的值。

3 2

2

7 7

818503

114514 233

782307368

提示

【样例 1 解释】
可以组成的合法排列有：$1,1,1$ 和 $2,2,2$
其余均不合法，都含有 $1 \sim 2$ 的排列，因此答案为 $2$。

【样例 2 解释】
总共有 $7^7$ 种情况，其中有 $7!$ 个不合法（即 $1 \sim 7$ 的排列情况数），答案为 $7^7-7!$，即 $818503$。

【数据范围】
对于 $100\%$ 的数据，$1\le k \le 10^4$，$1\le n \le 10^9$。

By：毕克