题目背景

小 L 曾经出了这样一个题：

给定长度为 $4$ 的整数序列 $c$，求是否存在长度为 $4$ 的整数序列 $a$ 满足 $0\le a_i\le c_i$ 且 $(((a_1\text{ and }a_2)\text{ xor }a_3)\text{ or }a_4=m$。

小 C 看到后觉得这个数位 DP 题非常板，很没意思。小 L 又修改上述问题的位运算的顺序，出了很多个题。

小 C 忍不了了：“你能不能别再出模板数位 DP 题了？”

小 L 只能把这一堆题交给了你。不过为了增加挑战性，现在你需要对所有可能的 $c_i$ 计算出答案并求和。

题目描述

给定长度为 $n-1$ 的字符串 $s$，对于一个长度为 $n$ 的非负整数序列 $a$，定义其生成序列 $b$ 为：

• $b_1=a_1$；
• 对于 $i>1$：
  • 若 $s_{i-1}=\verb!A!$，则 $b_i=b_{i-1}\text{ and }a_i$。
  • 若 $s_{i-1}=\verb!O!$，则 $b_i=b_{i-1}\text{ or }a_i$。
  • 若 $s_{i-1}=\verb!X!$，则 $b_i=b_{i-1}\text{ xor }a_i$。

给定非负整数 $k$。接下来 $q$ 组询问，每次给定一个 $m$，求有多少长度为 $n$ 的整数序列 $c$ 满足：

• 对于 $1\le i\le n$，满足 $0\le c_i<2^k$。
• 存在至少一个长度为 $n$ 的整数序列 $a$ 满足：
  • 对于 $1\le i\le n$，满足 $0\le a_i\le c_i$。
  • 对于 $a$ 的生成序列 $b$，满足 $b_n=m$。

由于答案很大，你只需要输出答案对 $2^{32}$ 取模的结果。

输入格式

第一行三个整数 $n,k,q$。

第二行一个长度为 $n-1$ 的字符串 $s$。

接下来 $q$ 行，每行一个询问的 $m$。

输出格式

输出 $q$ 行，每行一个非负整数，表示答案对 $2^{32}$ 取模的结果。

3 1 2
OA
0
1

8
3

4 2 2
XOA
1
2

189
112

4 2 3
XAO
1
2
3

237
176
143

10 10 3
AOOXOAOXA
749
666
135

4239261913
1948492800
2799056799

提示

本题使用捆绑测试，你只有通过一个子任务的所有测试点，才能获得这个子任务的分数。

子任务编号	$n\le$	$k\le$	$q\le$	特殊性质	分值
$1$	$4$	$5$	$200$	无	$10$
$2$	$20$	$8$	$20$
$3$	$200$	$16$	$1$
$4$			$200$
$5$		$30$	$1$	$\text{popcount}(m)\le 16$
$6$	$1000$		$1000$	$s$ 不包含 $\verb!A!$
$7$	$50$		$50$	无
$8$	$1000$		$1$
$9$	$200$		$200$
$10$	$1000$		$1000$

对于 $100\%$ 的数据，$2\le n\le 1000$，$1\le q\le 1000$，$1\le k\le 30$，$0\le m<2^k$。