32164번 - 지워진 ETT

문제

ETT-배열을 루트가 1ドル$인 트리를 다음과 같이 왼쪽 자식 우선으로 깊이 우선 순회하면서 진입 시점, 진출 시점에 맞춰 정점 번호를 순서대로 기록한 배열이라고 하자. 단, 리프 노드의 경우에도 진입 시점과 진출 시점에 모두 기록하므로, 노드가 $n$개인 트리에 대응되는 모든 ETT-배열은 길이가 2ドルn$이다.

[画像:그림의 트리를 순회하여 기록한 ETT-배열은 [1, 2, 2, 3, 3, 4, 4, 1]임]

위 트리를 순회하여 기록한 ETT-배열은 $[1,3,2,2,3,4,4,1]$이다.

0ドル$ 이상 $n$ 이하의 정수로 이루어진 길이가 2ドルn$인 배열이 주어질 때, 배열 속 모든 0ドル$을 1ドル$ 이상 $n$ 이하의 정수로 바꾸어서 만들 수 있는 모든 ETT-배열의 개수를 구하여라.

입력

첫 번째 줄에 $n$이 주어진다. (1ドル\le n\le 200$)

두 번째 줄에 배열을 나타내는 정수 $a_1,ドル $a_2,ドル $\cdots,ドル $a_{2n}$이 공백으로 구분되어 주어진다. (0ドル\le a_i\le n$; $a_1=a_{2n}=1$)

주어지는 배열로 적어도 하나의 ETT-배열을 만들 수 있다.

출력

답을 998ドル,244円,353円$으로 나눈 나머지를 출력한다.

제한

노트