19317번 - Hanoi 다국어

문제

Rikka has $n$ disks of distinct sizes on three rods. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. No disk can be placed on top of a smaller disk.

Given the configuration of disks $S$ and $T,ドル find the number of ways can Rikka transform from $S$ to $T$ in no more than $m$ moves.
As the number of ways can be very large, find it modulo 998ドル,244円,353円$.

Two sequences of moves are different if they have different lengths, or the configurations are different after some moves.

입력

The first line contains two integers $n$ and $m$ (1ドル \leq n \leq 100,ドル 0ドル \leq m \leq 100$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n,ドル the configuration $S$ (1ドル \le a_i \le 3$). These mean that the $i$-th smallest disk is on rod $a_i$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n,ドル the configuration $T$ given in the same format (1ドル \le b_i \le 3$).

출력

Print one integer: the number of ways modulo 998ドル,244円,353円$.

제한

힌트