Description

给定n个小写字符串，考虑 n!种连接它们的顺序，问有多少种连接顺序最后得到的字符串有偶数个本质不同的子序列。

n ≤ 20。 ∑ len ≤ 100000。

Format

Input

第一行给出数字N，接下来N行每行一个字符串

Output

如题

Samples

4
ab
abb
bc
cd

16