题目描述

本来今天小 $Q$ 是想让你补全一个矩阵的，但是他突然发现自己把矩阵剩下部分的信息也搞丢了。

具体来讲，他的矩阵是一个 $n$ 行 $m$ 列的 $01$ 矩阵 $A$ （下标从 $0$ 开始），有如下性质：

$1.$ 把每一行的值拼起来形成一个二进制数，那么这个数属于一个给定的集合 $S$ ，即满足

$$\forall 0 \le i \lt n, S \ni \sum\limits^{m-1}_{j=0} a_{ij}2^j $$

$2.$ 对于每一列的性质，我们用两个长度为 $m$ 的数组 $b$ （ $b_i \in [0, 3]$ ）和 $c$ （ $ci \in [0, 1]$ ）来描述。对于每个 $0 \le i \lt m$ ：

• 若 $b_i = 0$ ，则满足第 $i$ 列的每个元素都等于 $c_i$ ； • 若 $b_i = 1$ ，则满足第 $i$ 列的所有元素的 按位或 和等于 $c_i$ ； • 若 $b_i = 2$ ，则满足第 $i$ 列的所有元素的 按位与 和等于 $c_i$ ； • 若 $b_i = 3$ ，则满足第 $i$ 列的所有元素的 按位异或 和等于 $c_i$ 。

不幸的是，小 $Q$ 把数组 $c$ 也给搞忘了，只记得 $S$ 和 $b$ ，所以你需要帮助他回忆起数组 $c$ 。

具体而言，他会向你询问 $Q$ 次，每次给出一个可能的 $c$ ，你需要回答满足条件的矩阵的个数。

输入格式

第一行两个正整数 $n$ 和 $m$ ，表示矩阵的行数和列数； 第二行一个长度为 $2^m$ 的 $01$ 字符串 $T$ ，第 $i$ 个位置为 $1$ 表示 $i \in S(0 \le i \lt 2^m)$ ，易知不在此范围的数不影响答案； 第三行 $m$ 个数表示数组 $b$ ； 第四行一个正整数 $Q$ ，表示询问次数； 接下来 $Q$ 行，每行一个整数 $x$ ，表示把给出的数组 $c$ 拼成二进制数的结果，即满足 $x =\sum^{m-1}_{i=0}c_i2^i$ 。

输出格式

对于每次询问，输出满足条件的矩阵个数。由于数值可能很大，你只需要输出答案取模 $10^9 + 7$ 的结果。

数据范围

对于所有测试点：对于所有测试点， $1 \le n \le 10^9, 1 \le m \le 20, 1 \le Q \le 10^5, b_i \in [0, 3], 0 \le x \lt 2^m$ 。

每个测试点的具体限制见下表：

测试点编号	$n \le$	$m \le$	$b_i \in$
$1 \sim 5$	$30$	$10$	$\{0, 1, 2, 3\}$
$6 \sim 10$	$10^9$
$11 \sim 15$		$20$	$\{1\}$
$16 \sim 20$		$17$	$\{0, 1\}$
$21 \sim 25$		$20$
$26 \sim 35$		$17$	$\{0, 1, 2, 3\}$
$36 \sim 50$		$20$

输入样例 1

2 2
0101
1 2
4
0
1
2
3

输出样例 1

0
3
0
1