대칭 선택의 개수

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

요약

길이 n인 두 단어 열이 주어질 때, 각 위치에서 두 단어 중 하나를 골라 이어 붙였을 때 회문이 되는 선택의 수를 센다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열, 투 포인터, 재귀
정답자: 아직 제출이 없습니다

문제

두 개의 단어 수열 $(x_1, \dots, x_n)$ 과 $(y_1, \dots, y_n)$ 이 주어진다. 여기서 $1 \le n \le 30$ 이다.

각 인덱스 $i$ ( $1 \le i \le n$ ) 마다 두 단어 $x_i$ 와 $y_i$ 중 정확히 하나를 고른다. 고른 단어들을 인덱스가 커지는 순서대로 이어 붙인다. 따라서 하나의 선택은 길이 $n$ 인 수열로 나타낼 수 있으며, 그 $i$ 번째 원소는 $1$ ( $x_i$ 를 고름) 또는 $2$ ( $y_i$ 를 고름) 이다. 가능한 선택은 모두 $2^n$ 가지이다. 서로 다른 선택이 같은 단어를 만들 수도 있다.

어떤 선택으로 만들어진 단어가 팰린드롬(왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같은 단어)이면, 그 선택을 대칭적이라고 부른다.

두 수열이 주어질 때, $2^n$ 가지 선택 중 대칭적인 선택이 몇 개인지 구하라.

입력

첫째 줄에 정수 $n$ ( $1 \le n \le 30$ ) 이 주어진다.

이어지는 $n$ 개의 줄에는 첫 번째 수열의 단어들이 한 줄에 하나씩 순서대로 주어진다. 즉 $1+i$ 번째 줄이 $x_i$ 이다 ( $i = 1, \dots, n$ ). 그다음 $n$ 개의 줄에는 같은 방식으로 두 번째 수열의 단어들이 주어진다. 즉 $1+n+i$ 번째 줄이 $y_i$ 이다.

각 단어는 비어 있지 않은 소문자 알파벳(a 부터 z) 문자열이다. 모든 단어 길이의 합은 $1$ 이상 $400$ 이하이다.

출력

대칭적인 선택의 개수를 나타내는 음이 아닌 정수 하나를 출력한다.

예제3

예제 1
입력
```
5
ab
a
a
ab
a
a
baaaa
a
a
ba
```
예상 출력
```
12
```
예제 2
입력
```
1
aba
a
```
예상 출력
```
2
```
예제 3
입력
```
1
ab
ba
```
예상 출력
```
0
```