Description

给定长度为 $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}$ 取模的结果。

Input Format

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

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

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

Output Format

输出 $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

Hint

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

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