問題文

頂点に $1,2,\ldots,N$ と名前のついた $N$ 頂点の無向木に対して、$(1,2,\ldots,N)$ の順列 $X$ が Pruning Order であるとは、以下の条件を満たすことを言います。

• $i = 1,2,\ldots,N$ の順に、頂点 $X_i$ および頂点 $X_i$ を端点とする辺を全て削除する。この時、全ての $i = 1,2,\ldots,N - 1$ に対して、削除される直前に頂点 $X_i$ は葉となっている。

$(1,2,\ldots,N)$ の順列 $P,Q,R$ が与えられます。頂点に $1,2,\ldots,N$ と名前のついた無向木であって、$P,Q,R$ が全て Pruning Order となっているようなものの数を $M$ で割った余りを求めてください。

テストケースは全部で $T$ ケース与えられます。

制約

• $1 \le T \le 10^5$
• $1 \le N \le 10^5$
• $2 \le M \le 10^9$
• $P,Q,R$ は $(1,2,\ldots,N)$ の順列
• 全てのテストケースに対する $N$ の総和は $10^5$ 以下
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_i$ は $i$ 番目のテストケースです。

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられます。

$N \ M$
$P_{1} \ P_2 \ \ldots \ P_{N}$
$Q_{1} \ Q_2 \ \ldots \ Q_{N}$
$R_{1} \ R_2 \ \ldots \ R_{N}$

出力

$T$ 行出力してください。$i$ 行目には $\text{case}_i$ に対する答えを出力してください。

サンプル

3
4 5
1 4 2 3
3 1 2 4
4 1 3 2
3 2
1 2 3
1 2 3
2 3 1
20 998244353
18 14 17 15 6 9 19 12 16 13 10 11 4 20 7 5 8 3 1 2
18 20 7 17 19 3 13 15 6 2 5 14 4 11 10 16 9 1 8 12
20 14 7 18 12 15 16 11 10 3 9 19 8 17 2 4 1 6 5 13

1
1
44236800