[SDOI2006] 二进制方程

题目描述

一个形如: X1X2…Xn=Y1Y2..Ym 的等式称为二进制方程。 在二进制方程的两边:Xi和Yj (1<=i<=n;1<=j<=m)是二进制数字(0、1)或者一个变量(小写字母)。每个变量都是一个有固定长度的二进制代码,他可以在等式中取代变量的位置,称这个长度为变量的长度。为了解一个二进制方程,需要给其中的变量赋予适当的二进制代码,使得我们用他们替代等式中的相应的变量后(等式的两边都变成二进制代码),这个等式成立。 编程任务: 对于每一个给出的方程,计算一共有多少组解。已知变量最多有26个(26个英文小写字母),且等式的每一端的数字和变量的长度之和不超过10000。

输入输出格式

输入格式


第一行:k(k<=26,变量的个数,规定使用小写英文字母中的前k个字母作为变量,如k=5,则变量a,b,c,d,e)。 第二行:k个正整数,中间用一个空格隔开,依次代表k个变量的长度。 第三行:等式左边的表达式。 第四行:等式右边的表达式。

输出格式


等式中出现的变量共有多少组解。

输入输出样例

输入样例 #1

2
4 2
1b1
a

输出样例 #1

4

输入样例 #2

5
4 2 4 4 2
1bad1
acbe

输出样例 #2

16

说明

样例一:4组解 1 、a=1001; b=00 2、 a=1011; b=01 3、 a=1101; b=10 4、 a=1111; b=11) 样例二:K=5,变量:a,b,c,d,e。长度分别为:4 2 4 4 2。等式是:1bad1= acbe 输出16,即变量a,b,c,d,e共有16组解。