题目描述

定义 \(f(n)\) 为 \(n!\) 中素因子 \(2\) 的个数。例如， \(5! = 120 = 2^3 \times 3 \times 5\)，所以 \(f(5) = 3\)。

给出一个正整数序列 \(m_2, m_3, \ldots, m_n\) 和模数 \(Mod\)，yummy 有 \(Q\) 次询问，每次给定正整数 \(V\)，求：

有多少个单调不降的自然数序列 \(a_1, a_2, \ldots, a_n\) 满足 \(a_n \le V\)，并且对于所有 \(1 < i \le n\)，有 \(f(a_{i-1})\equiv f(a_i) \pmod{m_i}\)。

输入格式

第一行有三个正整数 \(n, Mod, Q\) （\(1 \le n \le 20\)， \(|Mod-10^9| \le 10^7\)， \(1 \le Q \le 100\)），分别表示待求序列长度，答案的模数，以及询问个数。

第二行有 \(n-1\) 个正整数 \(m_2, m_3\ldots, m_n\) （\(1 \le m_i \le 20\)， \(\sum m_i \le 200\)），含义见题目描述。

之后有 \(Q\) 行，每行有一个正整数 \(V\) （\(1 \le V \le 10^{18}\)），表示一次询问。

输出格式

对于每次询问，输出一行一个自然数，表示答案对 \(Mod\) 取余的结果。

样例输入

4 1001001001 2
2 4 1
4
3

样例输出

29
18

提示

对于第一个询问，注意到 \(i = 4\) 时， \(a_3 \equiv a_4 \pmod 1\) 是废话，也就是 \(a_4\) 仅受到 \(a_4 \ge a_3\) 的限制。

我们列举所有合法的 \((a_1, a_2, a_3)\)，将方案数相加即可得到总方案数 \(29\)：

前三项对应方案数前三项对应方案数前三项对应方案数 \(0, 0, 0\) \(5\) \(2, 2, 2\) \(3\) \(3, 3, 3\) \(2\) \(0, 0, 1\) \(4\) \(2, 2, 3\) \(2\) \(3, 4, 4\) \(1\) \(0, 1, 1\) \(4\) \(2, 3, 3\) \(2\) \(4, 4, 4\) \(1\) \(1, 1, 1\) \(4\) \(2, 4, 4\) \(1\)

对于第二个询问，我们可使用类似的方法求出答案。