HY 非常喜欢和GJQ 闲聊，而其他人等都还奋斗在OI 的道路上，为了不打扰同学，他们交流统一用密文，交流信息的明文是由0 和1 组成的非空序列，而密文是由0、1 和若干个密码字母组成，每个密码字母代表不同的01 串，例如，密文011a0bf00a01。密码破译的关键是确定每个密码的含义。

经过长期统计分析，现在知道了每个密码的固定长度，如今，蛋疼的同学们又截获了它们俩的两段密文S1 和S2 ，并且知道S1 = S2 ，即两段密文代表相同的明文。你的任务是帮助同学们对给定的两段密文进行分析，看一看有多少种可能的明文。

第1 行：S1 (第1 段密文)

第2 行：S2 (第2 段密文)

第3 行：N (密码总数，N ≤ 26)

第4-N+3 行：字母i 长度i (密码用小写英文字母表示，密码长度≤ 100)

M（表示有M 种可能的明文）

数据范围

明文的长度≤10000

保证不用高精度

Hint

对于本题，如果在并查集中存在x 个集合，那么可能的方案数便是2x。

解释一下样例：

由输入可知，a 的长度为2，d 的长度为3，c 的长度为4，b 的长度为50，那么我们便可以将100ad1

和cc1 展开成为下面的内容

1 0 0 a1 a2 d1 d2 d3 1

c1 c2 c3 c4 c1 c2 c3 c4 1

那么，在并查集操作后，将会有三个集合出现

1 c1 a2

0 c2 d1 c3 d2

d3 c4 a1
因为1和0是确定的，所以不确定的只有一个集合，那么答案便是21