Problem Statement

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.

Constraints

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

Input

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

Output

Output the answer.