logo AlgoBeat OnlineJudge
登录 注册

#102919. [BZOJ 2919] [Poi1998]Word equations

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一个非空的 元素的序列称作一个二进制单词。一个单词等式是一个形式为 的等式, 是二进制数字()或者为变量的英文大写字母。对于每个变量代替一个固定长度的二进制单词,这个长度称作变量的长度。为了解决一个单词等式我们必须给所有的变量分配适当长度的二进制单词(分配给变量 的单词长度必须等于这个变量的长度)。采用这种方式,如果用变量代替单词,那么等式的两边(替换后的二进制单词)相等。

对于一个给定的等式,计算它有多少种不同的方法使等式成立。

例如 是变量,它们的长度分别是 ,(即 的长度是 的长度是 )。

考虑等式:

这个等式有 种不同的方法能使等式成立。

你需要编写一个程序,寻找对于每个等式最多有多少种不同方法使等式成立。

输入格式

第一行有一个整数 ,表示等式的总数。

下面的行包含 个等式的描述,每个等式的描述包含 行,描述的等式间没有空行,每个等式的描述是:

  • 第一行有一个整数 ,表示等式中不同变量的个数,并且假定是用英文字母表中的前 个小写字母;
  • 第二行有 正整数,它们由空格分开,代表等式中 个变量的长度;
  • 第三行有一个整数 ,表示等式左边二进制单词的长度,这个长度包括 、及变量;
  • 第四行是等式左边的二进制单词;
  • 第五行有一个整数 ,表示等式右边二进制单词的长度;
  • 第六行是等式右边的二进制单词。

在等式两边的二进制单词的长度总和不超过

输出格式

对于每个询问,输出有多少种不同的方法使等式成立。

样例

样例输入 #1

1 
5
4 2 4 4 2
5
1BAD1
4
ACBE

样例输出 #1

16

数据范围与提示

对于 的数据,