전투력 비교

총 N개의 좌석이 일렬로 나열되어 있다. 또한 1번부터 N번까지 N명의 전사가 존재하며, 각 전사는 하나의 좌석에 배치해야 한다. 이때, 각 전사는 모두 개별적으로 전투력 정보를 가진다. 그리고 전투력 정보는 서로 동일할 수 있으며, 그 정보는 1부터 20까지의 자연수 형태의 값을 가진다.

이때, N명의 전사를 배치할 때, 인접한 좌석에 대하여 N-1개의 조건을 만족해야 한다. 조건은 1번부터 N-1번까지 존재하며, 그 의미는 다음과 같다.

1번 조건: 1번 좌석과 2번 좌석에 대한 조건 2번 조건: 2번 좌석과 3번 좌석에 대한 조건 … N-1번 조건: N-1번 좌석과 N번 좌석에 대한 조건

이때 각 조건은 1, 2, 3, 4중 하나의 자연수 형태의 값을 가지며, 그 의미는 다음과 같다.

1) 값이 1인 경우: 왼쪽 좌석에 앉은 전사가 오른쪽 좌석에 앉은 전사보다 전투력이 높다. 2) 값이 2인 경우: 왼쪽 좌석에 앉은 전사가 오른쪽 좌석에 앉은 전사보다 전투력이 낮다. 3) 값이 3인 경우: 왼쪽 좌석에 앉은 전사와 오른쪽 좌석에 앉은 전사의 전투력이 같다. 3) 값이 4인 경우: 해당 위치에서는 별도의 조건을 만족하지 않아도 된다.

결과적으로 조건에 부합하도록 전사를 배치하는 경우의 수를 출력하는 프로그램을 작성하여라.

예를 들어 N=5이고, 1번부터 N번까지의 전사에 대한 전투력이 차례대로 7, 10, 7, 5, 3이라고 해보자. 또한 조건이 3, 1, 2, 4라고 해보자. 이때, 다음과 같이 1번, 3번, 5번, 2번, 4번 순서대로 전사를 배치하면 다음과 같이 조건을 만족한다.

그림상에서 각 조건에 대하여 값이 1인 경우는 ">", 값이 2인 경우는 "<", 값이 3인 경우는 "=", 값이 4인 경우는 빈 상자로 표현했다.

> (원본 문서의 배치 그림이 텍스트 추출 과정에서 유실되었다.)

혹은 3번, 1번, 5번, 4번, 2번 순서대로 전사를 배치하여도 다음과 같이 조건을 만족하는 것을 확인할 수 있다.

> (원본 문서의 배치 그림이 텍스트 추출 과정에서 유실되었다.)

결과적으로 현재 예시에서 전사를 배치하는 경우의 수는 총 6가지다.

입출력 예시

예시 1

입력

5, [7, 10, 7, 5, 3], [3, 1, 2, 4]

출력

6

예시 2

입력

3, [4, 5, 6], [1, 2]

출력

2

원본에서 모의고사 1회 3번입니다.

조건을 설명하는 번호가 원본에 1) 2) 3) 3) 으로 매겨져 있다. 마지막 3) 이 네 번째 조건이다.