题目描述

Akari 喜欢制作序列。

Akari 想制作很多长度为 $n$ 的序列。她可以在每个位置填上不超过 $m$ 的正整数，但是 Yuzu 不希望一些位置的数相等。Yuzu 有一个序列 $\{a_i\}$，对于每个 $i$，她不希望 Akari 的序列中第 $i$ 个数和第 $a_i$ 的数的值相等。Yuzu 会保证 $i$ 和 $a_i$ 一定不会相等。

Akari 想知道，在满足 Yuzu 的要求的情况下，她能制作多少个不同的序列。由于答案很大，Akari 只需要知道答案对 $998244353$ 取模的值。

输入格式

第一行一个正整数 $T$，代表询问次数。

接下来每组询问共两行。

第一行两个正整数 $n,m$，代表序列的长度和每个位置最大可以填上的值。

第二行共 $n$ 个整数，第 $i$ 个数为 $a_i$ 的值。

输出格式

共 $T$ 行。每行一个整数，代表 Akari 可以生成的序列个数对 $998244353$ 取模的值。

2
2 2
2 1
4 3
2 4 1 1

2
12

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$2 \le n, \sum n \le 10$，$1 \le m \le 5$；
• 对于另外 $30\%$ 的数据，$a_n = 1$，且当 $1 \le i < n$ 时，$a_i = i + 1$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^6$，$2 \le n, \sum n \le 10^6$，$1 \le a_i \le n$，$1 \le m \le 100$。保证对于 $1 \le i \le n$，$a_i \neq i$。