你好，我是阿西莫夫。

在生物学中，减数分裂（Meiosis） 是生命遗传多样性的源泉。 当一个生物体产生配子（精子或卵子）时，成对的等位基因会分离，且不同性状的基因会自由组合。

比如，基因型为 AaBb 的个体，可以产生 AB, Ab, aB, ab 四种配子。 如果我们把显性基因（A, B）看作二进制的 1，隐性基因（a, b）看作二进制的 0，那么这四种配子就对应了 11, 10, 01, 00。

这道题将考察如何利用位运算（Bitmask）来快速验证配子的合法性，以及利用排列组合思维计算配子的种类。

[OI 题库] 孟德尔的“配子”密码 (Mendel's Gamete Code)

题目背景

“基因是生命的二进制代码，而减数分裂就是那个产生随机数的算法。”

你正在研究一种拥有 $N$ 对相对性状的转基因作物。每一对性状由一对等位基因控制，遵循孟德尔的自由组合定律。

• 显性基因用大写字母表示（如 A），对应二进制位 1。
• 隐性基因用小写字母表示（如 a），对应二进制位 0。

给定亲本的基因型，请你计算它能产生多少种不同的配子，并判断某些特定的配子是否可能由该亲本产生。

题目描述

亲本拥有 $N$ 对基因。 我们用一个长度为 $2N$ 的字符串 $S$ 来描述亲本的基因型。每两个字符代表一对基因（例如 Aa, BB, cc）。

你需要完成两个任务：

1. 计数：计算该亲本能通过减数分裂产生多少种不同的配子？
2. 验证：给定 $M$ 个询问，每个询问是一个整数 $X$。请判断整数 $X$ 的二进制形式所代表的配子，是否可能由该亲本产生？
   • 对应规则：整数 $X$ 的二进制位从低到高（第 0 位到第 $N-1$ 位），对应亲本基因型字符串从右到左（第 $N-1$ 对到第 0 对）。或者简单来说：字符串最左边的基因对对应最高位，最右边的基因对对应最低位。
   • 如果 $X$ 的第 $i$ 位是 1，代表该配子在第 $i$ 对性状上获得了显性基因。
   • 如果 $X$ 的第 $i$ 位是 0，代表该配子在第 $i$ 对性状上获得了隐性基因。

输入格式

第一行两个整数 $N, M$，分别表示性状对数和询问次数。 第二行一个字符串 $S$（长度为 $2N$），表示亲本基因型。 接下来 $M$ 行，每行一个整数 $X$，表示一个待验证的配子编码。

输出格式

第一行输出一个整数，表示不同配子的总数量。 接下来 $M$ 行，对于每个询问 $X$：

• 如果可能产生，输出 Yes。
• 如果不可能产生，输出 No。

样例数据

样例 1

3 4
AaBBcc
6
2
4
7

2
Yes
Yes
No
No

样例解析：

• 亲本基因型：AaBBcc
  • 第 2 对 (最高位): Aa (杂合)，配子该位可以是 0 或 1。
  • 第 1 对 (中间位): BB (显性纯合)，配子该位必须是 1。
  • 第 0 对 (最低位): cc (隐性纯合)，配子该位必须是 0。
• 合法配子：
  • 情况 A: A (1) B (1) c (0) $\to$ 二进制 110 $\to$ 十进制 6。
  • 情况 B: a (0) B (1) c (0) $\to$ 二进制 010 $\to$ 十进制 2。
  • 总共 2 种。
• 询问验证：
  • $X=6$ (110): 合法。输出 Yes。
  • $X=2$ (010): 合法。输出 Yes。
  • $X=4$ (100): 第 1 位是 0 (b)，但亲本只有 BB，矛盾。输出 No。
  • $X=7$ (111): 第 0 位是 1 (C)，但亲本只有 cc，矛盾。输出 No。

数据范围

• $1 \le N \le 30$ （保证 $2^N$ 可能会很大，但询问的 $X$ 在 int 范围内，组合数在 long long 范围内）。
• $1 \le M \le 100,000$。
• 字符串仅包含 AaBbCc... 等大小写字母。