Statement

给你$N$个字符串，分别为$S_1$、$S_2$、...、$S_N$，对于一个$1$到$N$的排列$P_1$、$P_2$、...、$P_N$，我们定义该排列下的"连接串"为$T$，$T=S_{P_1}+S_{P_2}+...+S_{P_N}$(其中"+"表示首尾相接)。询问有多少种$1$到$N$的排列满足对应的"连接串"的本质不同子序列个数为偶数(空串算子序列)。

Task

input

如下格式输入

$N$

$S_1$

$S_2$

...

$S_N$

output

输出一行一个正整数表示答案

Sample I

input

3
e
e
aee

output

4

Sample II

见下发文件中的 string2.in/string2.out。

Constraints

数据范围

对于所有数据，$N<=20$,$\Sigma |S_i|<=10^5$,所有字符串仅包含英文小写字母。

对于 $10\%$ 的数据，$N<=8$且$\Sigma |S_i| <=8$

对于 $20\%$ 的数据，$N<=8$且$\Sigma |S_i| <=100$

对于 $30\%$ 的数据，$N<=8$

对于 $50\%$ 的数据，$N<=13$

对于 $60\%$ 的数据，$N<=15$

对于 $70\%$ 的数据，$N<=17$

对于另外 $20\%$ 的数据，所有字符串仅包含前2个英文小写字母(a、b)