시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 3 3 42.857%

문제

We are given two sequences of words: (x1, ..., xn) and (y1, ..., yn), with 1 ≤ n ≤ 30. For every i, 1 ≤ i ≤ n, we chose one of the two words: xi or yi. The chosen words are merged in order of increasing indices. The choice consists of n steps. In each step we decide to take the i-th word from the first or from the second sequence of words. More formally: the choice is a sequence of length n whose elements are numbers 1 and 2. It is possible that different choices lead to the same word. We say that a choice is symmetrical if its result is a palindrome, i.e. a word that is identical when we read it from left to right and from right to left.

Write a program that:

  • reads from the standard input: the number n and two sequences of words (x1, ..., xn) and (y1, ..., yn),
  • computes the number of symmetrical choices for the given sequences,
  • writes the result to the standard output.

입력

In the first line of the standard input there is one positive integer n ≤ 30. In the following n lines there are written consecutive words of the sequence (xi) — one word in one line. In the following n lines there are written (in the similar way) consecutive words of the sequence (yi). Each word consists solely of small letters of the English alphabet (from a to z). The total length of all words is from the range [1..400].

출력

In the standard output there should be written one non-negative integer — the number of symmetrical choices.

예제 입력 1

5
ab
a
a
ab
a
a
baaaa
a
a
ba

예제 출력 1

12