最长待机（sleep）

题目描述

给定两个集合 $S,T$ 和一个整数 $n$，你需要求出有多少个序列 $a$ 满足以下条件：

• $0\le |a|\le n$。
• 对于所有 $1\le i\le |a|$，$a_i\in S$。
• 对于所有 $1\le i\le |a|-1$，$a_i\le a_{i+1}$。
• $\bigoplus_{i=1}^{|a|}a_i\in T$。

其中 $\oplus$ 表示二进制下按位异或。

$Test$ 组询问，每次 $S,T$ 不变，即给定 $n$ 求出答案对 $10^9+7$ 取模后的结果，强制在线。

输入格式

第一行两个整数 $|S|,|T|$，表示 $S,T$ 的大小。

第二行 $|S|$ 个整数表示 $S$。

第三行 $|T|$ 个整数表示 $T$。

第四行一个整数 $Test$ 表示数据组数。

接下来 $Test$ 行，每行三个整数 $n',a,b$，每次你的 $n$ 等于 $(n'\oplus(ans+b))\bmod a$，其中 $ans$ 是上一次询问输出的答案，初始为 $0$，$\oplus$ 表示二进制下按位异或。

输出格式

输出 $Test$ 行，每行一个整数表示答案。

样例 1 输入

3 1
1 2 3
0
1
2 100 1

样例 1 输出

5

样例 1 解释

$a$ 共有 $5$ 种选择：$[]$，$[1,1]$，$[2,2]$，$[3,3]$，$[1,2,3]$。

数据范围

对于 $100\%$ 的数据，满足 $1\le Test\le 10^5$，$0\le S_i,T_i<2^{28}$，$1\le |S|,|T|\le 2^7$，$1\le n',a,b\le 10^8$。不保证 $S,T$ 中元素互不相同。

• 特殊性质 A：保证 $S$ 中的元素线性无关，即不存在两个 $S$ 的不同非空子集 $T_1,T_2$ 满足 $T_1$ 中所有元素的异或和等于 $T_2$ 中所有元素的异或和。
• 特殊性质 B：保证 $T$ 中的元素大小不超过 $3$。