Combinatorics PTSD

时间限制：1s

空间限制：64MB

题目描述

\[\bold{Calculate\ \ \ {\LARGE |} \{\bold{(a_0,a_1...a_{n-1})}\ {\big |}\ \forall i\in \{0,1,..., n-1\},a_i\in \{1,2,...,k\} ∧ a_i\neq a_{((i+1)\mod n)}\}{\LARGE |} \mod 998244353}\]

输入格式

两个正整数 \(n,k\) ，同题目描述所示。

输出格式

输出答案，注意，方案数需要对 998244353 取模。

样例输入1

3 3

样例输出1

6

样例1解释

题意翻译

\((1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\) 一共六种符合条件的3元组。

样例输入2

4 4

样例输出2

84

样例2解释

部分可行的方案：

(1,2,1,2)(1,2,1,3)(1,2,1,4)(1,2,3,2)(1,2,3,4)(1,2,4,2)(1,2,4,3)(1,3,1,2)(1,3,1,3)(1,3,1,4)

(1,3,2,3)(1,3,2,4)

样例输入3

1926 817

样例输出3

164477364

数据范围

对于 50 % 的数据，\(2\le n,k\le 8\)

对于 100 % 的数据，\(2\le n,k \le 3*10^3\)

• bonus: 如何对于 \(2\le n,k\le 10^{18}\) 求解？