하노이

시간 제한1초메모리 제한256 MB

요약

최대 m번 이동으로 하노이 상태 S를 T로 바꾸는 이동 순서의 개수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 재귀, 조합론
정답자: 아직 제출이 없습니다

문제

Rikka는 크기가 모두 다른 원판 $n$ 개를 세 막대 위에 놓아 두었다. 한 번의 이동에서는 어느 스택의 맨 위 원판을 꺼내 다른 스택의 맨 위에 올려놓는다. 원판은 자기보다 작은 원판 위에 올릴 수 없다.

원판 배치 $S$ 와 $T$ 가 주어진다. Rikka가 $S$ 를 $m$ 번 이하의 이동으로 $T$ 로 바꾸는 방법의 수를 구하라. 이동 순서는 길이가 다르거나, 어떤 이동 후의 배치가 다르면 서로 다른 것으로 본다. 방법의 수를 $998\,244\,353$ 으로 나눈 나머지를 출력하라.

입력

첫 번째 줄에 두 정수 $n$ , $m$ ( $1 \leq n \leq 100$ , $0 \leq m \leq 100$ )이 주어진다.

두 번째 줄에는 배치 $S$ 를 나타내는 정수 $n$ 개 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 3$ )이 주어진다. 이는 $i$ 번째로 작은 원판이 막대 $a_i$ 위에 있다는 뜻이다.

세 번째 줄에는 같은 형식으로 배치 $T$ 를 나타내는 정수 $b_1, b_2, \ldots, b_n$ ( $1 \le b_i \le 3$ )이 주어진다.

출력

방법의 수를 $998\,244\,353$ 으로 나눈 나머지를 정수 하나로 출력한다.

예제4

예제 1
입력
```
1 2
1
3
```
예상 출력
```
2
```
예제 2
입력
```
2 4
1 1
1 2
```
예상 출력
```
4
```
예제 3
입력
```
1 2
1
1
```
예상 출력
```
3
```
예제 4
입력
```
3 10
1 1 1
2 1 3
```
예상 출력
```
149
```