Rikka 有 $n$ 个大小各不相同的圆盘，放置在三根柱子上。每次移动操作包括：从某一根柱子的顶部取出一个圆盘，并将其放置在另一根柱子的顶部。任何圆盘都不能放置在比它小的圆盘之上。

给定圆盘的初始状态 $S$ 和目标状态 $T$，求 Rikka 在不超过 $m$ 次移动内，将状态从 $S$ 变换到 $T$ 的方案数。由于方案数可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

如果两个移动序列的长度不同，或者在某次移动后圆盘的配置不同，则认为这两个序列是不同的。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100, 0 \le m \le 100$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始状态 $S$ ($1 \le a_i \le 3$)。这意味着第 $i$ 小的圆盘位于第 $a_i$ 根柱子上。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示目标状态 $T$，格式与 $S$ 相同 ($1 \le b_i \le 3$)。

输出格式

输出一个整数：方案数对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

1 2
1
3

样例输出 1

2

样例输入 2

2 4
1 1
1 2

样例输出 2

4

样例输入 3

1 2
1
1

样例输出 3

3

样例输入 4

3 10
1 1 1
2 1 3

样例输出 4

149