题目描述

给定两个单词序列：$x_1,x_2,\dots,x_n$ 与 $y_1,y_2,\dots,y_n$。我们每次从两个序列中选取 $x_i$ 或 $y_i$ 中的一个，将被选择的单词将从左到右进行合并。共做 $n$ 次选择。每一步我们都可以从两个序列中的任意一个拿走一个单词。也就是说：最终的选择都是由 $1$ 和 $2$ 组成的一个长度为 $n$ 的序列。当然不同选择方式，最终可能组成同一个单词。

如果一个选择的结果是可逆的，则我们说这种选择是对称的选择。例如：一个单词从左到右和从右到左读都相同。

你需要写一个程序来计算对称选择的数目。

输入格式

第一行是一个正整数 $n$，下面 $n$ 行是连续的第一个序列，其中每一行为一个单词 $x_i$，接下来是第二个序列，每一行为一个单词 $y_i$。

单词全部由小写的英文字母组成。

输出格式

输出非负整数，为对称选择的数目。

5
ab
a
a
ab
a
a
baaaa
a
a
ba

12

数据规模与约定

对于 $100\%$ 的数据，$n\le 30$，$1\le$ 单词的长度 $\le400$。