致两千年后的你

题号：NC212002
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛给你了 $n$ 个数 $a_{1,2...n}$ ，同时他对于非空集合 $S$ ，定义 $f_0(S)$ 表示其是否合法，其中 $f_0(S)$ 的值关乎于两个常数 $x$ 和 $P$ 。

形式化的说，集合 $S$ 合法当且仅当存在一组系数 $c$ 使得：

$\bigg(\sum_{i\in S} a_i\times c_i\bigg)\equiv x\pmod P$

此时 $f_0(S)=1$ ，否则 $f_0(S)=0$

对于 $k\ge 1$ ，定义 $f_k(S)=\sum_{T\subseteq S,T\ne \varnothing} f_{k-1}(T)$ ，即 $f_k(S)$ 为 $S$ 的所有子集 ${T}$ 的 $f_{k-1}(T)$ 的和。

现给定 $n$ 个数 $a_{1...n}$ ，进行 $T$ 组查询，每次给定 ${x,k,P}$ ，求 $f_k(U)$ ，其中 ${U}$ 表示全集。由于结果可能很大，答案需要对 $10^9+7$ 取模。


第一行两个正整数依次表示 n, T


接下来一行 n 个正整数，第 i 个正整数表示  

接下来 T 行，每行三个正整数，依次表示 x, k, P

输出共 T 行，每行一个正整数，表示  对   取模的结果。

示例1

复制

复制

6
15

对于第一组查询 k=1，等价于求有多少个非空集合合法，不难注意到总共有 7 个集合，其中当集合为  时非法，其余情况均合法。

对于第二组查询，，不难注意到：



而  为他们的和，即

示例2

复制

7 5
3 5 2 12 1 6 7 
1 1 6
10 1 2
3 2 10
7 3 6
7 4 3

复制

保证  ，保证  的最大质因子   。