OI题库

所有非空的01序列被称作一个二进制单词。一组相等的单词是如下形式的等式：x1x2..xl=y1y2..yr ，这里xi 和yj 是二进制字符01或是用小写字母表示的变量。对每一个变量都有一个固定长度的两进制单词来代替这个变量，这个长度称之为这个变量的长度。为了解决单词相等 的问题我们需要用某种方法分配给所有变量适当的二进制单词（这个二进制单词的长度必须为这个变量的长度），使得变量被取代后的等式成立。对一个给定的等式 计算有几种解答。

例子：

让a,b,c,d,e分别为长度为4，2，4，4，2的5个变量。考虑以下等式：1bad1=acbe。这个等式有16种不同的解答方案。

任务：

写一个程序：

• 从文件中读入等式的数目以及它们的描述。
• 对每个等式找出它们的解答方案数。
• 将结果写入文件。

输入：

在文件的第一行有一个整数x(1<=x<=5)表示等式的数目，随后有x个等式的描述。每个描述包括6行，两个等 式的描述之间没有空行。每个等式用以下方式描述：在描述的第一行有一个整数k(0<=k<=26)表示等式中不同的变量数目，我们假设变量是 从a起的k个小写字母。第二行有k个由空格隔开的正整数，表示k个变量的长度（第一个数表示a的长度，第二个数表示b的长度）。第三行有一个整数l，表示 等式左边的长度（有0 1及变量（单个字母）组成的单词长度）。等式左边将被写在下一行，仅包括01及小写字母而没有空格。以下两行给出了对等式左边的描述，第一行为一个正整数 r，表示等式右边的长度，等式的右边被写在第二行。等式两边所有变量的和相等且不超过10000。

输出：

对每个I (1<=I<=x)，你的程序必须在第I行给出第I个等式的不同解答方案数，并将它写入文件。

输入样例：

1
5
4 2 4 4 2
5
1bad1
4
acbe

输出样例：

16