题目背景

小 $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} = A$，则 $b_i = b_{i-1} \, \text{and} \, a_i$。
  • 若 $s_{i-1} = O$，则 $b_i = b_{i-1} \, \text{or} \, a_i$。
  • 若 $s_{i-1} = 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}$ 取模的结果。

样例

样例输入 #1

3 1 2
OA
0
1

样例输出 #1

8
3

样例输入 #2

4 2 2
XOA
1
2

样例输出 #2

189
112

样例输入 #3

4 2 3
XAO
1
2
3

样例输出 #3

237
176
143

样例输入 #4

10 10 3
AOOXOAOXA
749
666
135

样例输出 #4

4239261913
1948492800
2799056799

提示

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

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