[Poi1997]The Number of Symmetrical Choices

时间限制:1s      空间限制:128MB

题目描述

给定两个单词序列:(x1,...,xn) and (y1,...,yn), 1 <= n <= 30。我们每次从两个序列中选取xi 或 yi中的一个,将被选择的单词将从左到右进行合并。共做n选择。每一步我们都可以从两个序列中的任意一个拿走一个单词。也就是说:最终的选择都是由1和2组成的一个长度为n的序列。当然不同选择方式,最终可能组成同一个单词。 如果一个选择的结果是可逆的,则我们说这种选择是对称的选择。例如:一个单词从左到右和从右到左读都相同。
任务
写一个程序:
  • 中读入数n和两个单词序列(x1,...,xn) 和 (y1,...,yn),
  • 从被给的序列中选择单词,计算对称选择的数目


输入格式

 第一行是一个正整数n, n <= 30. 下面N行是连续的第一个序列,其中每一行为一个单词 (xi),接下来是第二个序列,每一行为一个单词 (yi).单词 全部由小写的英文字母组成 (从a到 z),单词的长度为[1..400].


输出格式

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


样例输入

5
ab
a
a
ab
a
a
baaaa
a
a
ba


样例输出

12

提示

没有写明提示


题目来源

没有写明来源