AT_arc228_a.Row and Col swap

You are given permutations $P=(P_1,P_2,\dots,P_N)$ and $Q=(Q_1,Q_2,\dots,Q_N)$ of $(1,2,\dots,N)$.

For $P$ and $Q$, you repeat the following $M$ times: choose and perform one of the operations below.

• Choose integers $i$ and $j$ satisfying $1 \le i < j \le N$, and swap $P_i$ and $P_j$.
• Choose integers $i$ and $j$ satisfying $1 \le i < j \le N$, and swap $Q_i$ and $Q_j$.
• Choose an integer $i$ satisfying $1 \le i \le N$, and swap $P_i$ and $Q_i$.

Find the number, modulo $998244353$, of sequences of operations such that both $P$ and $Q$ are permutations of $(1,2,\dots,N)$ after the $M$ operations.

给你两个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$ 和 $Q=(Q_1,Q_2,\dots,Q_N)$。

对 $P$ 和 $Q$，重复执行以下操作共 $M$ 次：

• 选择满足 $1 \le i < j \le N$ 的整数 $i$ 和 $j$，交换 $P_i$ 与 $P_j$；
• 选择满足 $1 \le i < j \le N$ 的整数 $i$ 和 $j$，交换 $Q_i$ 与 $Q_j$；
• 选择满足 $1 \le i \le N$ 的整数 $i$，交换 $P_i$ 与 $Q_i$。

求满足“经过 $M$ 次操作后，$P$ 和 $Q$ 均仍为 $(1,2,\dots,N)$ 的排列”的操作序列的个数，答案对 $998244353$ 取模。

The input is given from Standard Input in the following format:

$N$ $M$
$P_1\ P_2\ \dots\ P_N$
$Q_1\ Q_2\ \dots\ Q_N$

输入从标准输入中按以下格式给出：

$N$ $M$
$P_1\ P_2\ \dots\ P_N$
$Q_1\ Q_2\ \dots\ Q_N$

Output the answer.

输出答案。

Sample 1 Explanation:
For example, the following sequence of operations satisfies the condition.

• Choose $i = 1$ in an operation of the third kind to swap $P_1$ and $Q_1$. Now $P=(1,2,3)$ and $Q=(1,3,2)$.

Any sequence of operations composed of exactly one of the following seven operations satisfies the condition: the three operations that swap two elements of $P$, the three operations that swap two elements of $Q$, and the operation described above that swaps $P_1$ and $Q_1$.

Constraints

• $1 \le N,M \le 500$
• $P$ and $Q$ are permutations of $(1,2,\dots,N)$.
• All input values are integers.

样例 1 解释：
例如，以下操作序列满足条件。

• 在第三类操作中选择 $i = 1$，交换 $P_1$ 和 $Q_1$。此时 $P=(1,2,3)$，$Q=(1,3,2)$。

任何恰好由以下七种操作之一构成的操作序列均满足条件：三类交换 $P$ 中两个元素的操作、三类交换 $Q$ 中两个元素的操作，以及上述交换 $P_1$ 和 $Q_1$ 的操作。

限制条件

• $1 \le N,M \le 500$
• $P$ 和 $Q$ 均为 $(1,2,\dots,N)$ 的排列。
• 所有输入值均为整数。