대칭 선택의 개수

두 개의 단어 수열 $(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$ 이하이다.

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