「POI 2023/2024 R3」Żyrandol

题目描述

题目译自 XXXI Olimpiada Informatyczna – III etap Żyrandol

Bajtazar 为宽敞客厅购置了一盏巨型吊灯。这盏吊灯需从零件组装，包含无限多个编号从 $1$ 开始的灯座和无限多个连接件，可连接两个灯座。

灯座分 $k$ 种类型（$k$ 为奇数，符合制造商喜好），按编号循环为类型 $1, 2, \ldots, k, 1, 2, \ldots$。类型 $t$ 的灯座顶部有一个挂钩，可连接上方灯座；底部有 $t$ 个挂钩，可连接下方灯座。灯座 $1$ 的顶部挂钩用于固定至天花板。

Bajtazar 按说明组装：从灯座 $1$ 开始，依次取最小编号的未连接灯座，将其底部挂钩与编号最小的未连接灯座的顶部挂钩相连。例如，若 $k=3$，灯座 $1$（类型 $1$）连接灯座 $2$；灯座 $2$（类型 $2$）连接灯座 $3, 4$；灯座 $3$（类型 $3$）连接灯座 $5, 6, 7$；灯座 $4$（类型 $1$）连接灯座 $8$，依此类推。参见下图。

为避免无限组装，Bajtazar 考虑 $q$ 个场景。第 $i$ 个场景中，他组装距天花板距离不超过 $p_i$ 的所有灯座。距离定义为：灯座 $1$ 距离 $1$；若灯座 $x$ 首次连接至灯座 $y$，则 $x$ 距离为 $y$ 距离加 $1$。如上例，灯座 $1$ 距离 $1$，灯座 $2$ 距离 $2$，灯座 $3, 4$ 距离 $3$，灯座 $5, 6, 7, 8$ 距离 $4$。

每个场景包含序列 $d_i$ 个类型 $a_{i,j}$，Bajtazar 想知道有多少长度为 $d_i$ 的不同灯座编号序列 $b_{i,j}$，满足：

• 对每个 $j$ $(1 \leq j \leq d_i)$，灯座 $b_{i,j}$ 类型为 $a_{i,j}$；
• 对每个 $j$ $(1 \leq j < d_i)$，灯座 $b_{i,j}$ 连接至 $b_{i,j+1}$。

因答案可能极大，需输出模 $10^9+7$ 的结果。你的任务是为每个场景计算此数量。

---

输入格式

第一行包含两个整数 $k, q$ $(1 \leq k < 10^7, k$ 为奇数$, 1 \leq q \leq 200000)$，表示灯座类型数和场景数。

接下来的 $2q$ 行描述 $q$ 个场景，第 $i$ 个场景占两行：

• 第一行包含两个整数 $d_i, p_i$ $(1 \leq d_i \leq 10^6, 1 \leq p_i \leq 10^9)$，表示序列长度和距离限制。
• 第二行包含 $d_i$ 个整数 $a_{i,j}$ $(1 \leq a_{i,j} \leq k)$，表示灯座类型序列。

设 $S$ 为所有 $d_i$ 之和，满足 $S \leq 10^6$。

输出格式

输出 $q$ 行，每行一个整数，表示对应场景的序列数量模 $10^9+7$。

---

样例

输入

3 4
3 3
3 2 1
3 4
2 3 2
3 4
3 1 2
1 5
1

输出

2
2
0
6

样例解释

• 场景 1：$d_1=3, p_1=3$，类型序列 $3, 2, 1$，有序列 $3, 2, 1$ 和 $3, 2, 4$（距离 $3, 2, 1$）。
• 场景 2：$d_2=3, p_2=4$，类型序列 $2, 3, 2$，有序列 $5, 3, 2$ 和 $2, 3, 5$。序列 $5, 3, 5$ 和 $2, 3, 2$ 因重复编号无效。
• 场景 3：$d_3=3, p_3=4$，类型序列 $3, 1, 2$，无满足条件的序列。
• 场景 4：$d_4=1, p_4=5$，类型序列 $1$，有 $6$ 个类型 $1$ 的灯座（编号 $1, 4, 8, 10, 13, 16$，距离 $\leq 5$）。

---

** 附加样例**

• $k=9$，查询为无限吊灯中的不同序列，满足子任务 $1$。
• $k=123$，查询为短序列，满足子任务 $2$。
• $k=9999999, q=S=200000$，满足子任务 $3$。
• $k=199999$，单查询序列长度 $200000$，满足子任务 $4$。
• $k=7654321$，单查询序列长度 $1000000$，满足子任务 $5$。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$k \leq 10, p_i \leq 10, S \leq 100$	4
2	$k, p_i, S \leq 1000$	16
3	$p_i \leq 1000000$	22
4	$k, S \leq 200000$
5	$S \leq 200000$	16
6	无附加限制	20

每个子任务中，含 $d_i=1$ 的测试组占 $50\%$ 分数。