Bajtazar 买了一个巨大的吊灯安装在他的宽敞客厅里。和商店里买来的家具一样，它需要用提供的零件组装起来。吊灯的零件集由无限多个灯座组成，这些灯座按顺序编号为从 1 开始的整数，以及无限多个可以连接两个灯座的连接器。

每个灯座属于 $k$ 种类型之一，且由于生产商的喜好，数字 $k$ 是奇数。按编号顺序，灯座的类型依次为 $1, 2, \dots, k, 1, 2, \dots, k, 1, 2, \dots, k, \dots$。每个类型为 $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$ 个场景中，Bajtazar 将组装所有距离天花板不超过 $p_i$ 的灯座。距离天花板的距离定义如下：灯座 1 的距离为 1，如果灯座 $x$ 第一次与灯座 $y$ 连接，则灯座 $x$ 的距离比灯座 $y$ 的距离大 1。在上面的例子中，灯座 1 的距离为 1，灯座 2 的距离为 2，灯座 3 和 4 的距离为 3，灯座 5、6、7 和 8 的距离为 4。

第 $i$ 个场景的描述还包含一个长度为 $d_i$ 的序列 $a_{i,j}$。它们表示 Bajtazar 想知道有多少个包含 $d_i$ 个不同灯座编号的序列 $b_{i,j}$，使得对于每个 $j$ ($1 \le j \le d_i$)，灯座 $b_{i,j}$ 的类型为 $a_{i,j}$，并且对于每个 $j$ ($1 \le j < d_i$)，灯座 $b_{i,j}$ 与灯座 $b_{i,j+1}$ 相连。由于这个数字可能非常大，他只需要结果对 $10^9 + 7$ 取模的值。你的任务是为 Bajtazar 考虑的每个场景计算这个数字。

输入格式

输入的第一行包含两个整数 $k$ 和 $q$ ($1 \le k < 10^7$, $k$ 是奇数，$1 \le q \le 200\,000$)，分别表示灯座类型的数量和 Bajtazar 考虑的场景数量。

接下来的 $2q$ 行包含 $q$ 个场景的描述；第 $i$ 个场景包含两行。第一行包含两个整数 $d_i, p_i$ ($1 \le d_i \le 10^6, 1 \le p_i \le 10^9$)，表示序列的长度和距离天花板的距离限制。第二行包含 $d_i$ 个整数，其中第 $j$ 个数为 $a_{i,j}$ ($1 \le a_{i,j} \le k$)。

令 $S$ 表示所有 $d_i$ 的总和。满足 $S \le 10^6$。

输出格式

你的程序应输出 $q$ 行，包含对 Bajtazar 各个场景的回答。

样例

输入 1

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

输出 1

2
2
0
6

说明 1

在第一个场景中，恰好有两个灯座编号序列：3, 2, 1 和 3, 2, 4。 在第二个场景中，也恰好有两个灯座编号序列：5, 3, 2 和 2, 3, 5。请注意，不应考虑序列 5, 3, 5 和 2, 3, 2，因为这些序列中的灯座编号有重复。 在第三个场景中，在距离天花板不超过 4 的灯座中，不存在类型依次为 3, 1, 2 的灯座序列。 在第四个场景中，我们询问距离天花板不超过 5 的类型为 1 的灯座数量；共有 6 个。

子任务

测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试组组成。

在每个子任务中，都存在满足对每个 $i$ 都有 $d_i = 1$ 的测试组，这些测试组占该子任务分值的 50%。