题目描述

记 ++ 表示两个序列的连接。例如：

$$[1,2,3]++[4,5,6]=[1,2,3,4,5,6].$$

定义函数 $\operatorname{inc}$：

$$\operatorname{inc}([a_0,\ldots,a_{n-1}],k,s)=[(a_0+k)\bmod s,\ldots,(a_{n-1}+k)\bmod s].$$

递归定义序列族 $FFT$：

$$FFT(0,s)=[0],$$ $$FFT(k+1,s)=\operatorname{inc}(FFT(k,s),0,s)++\operatorname{inc}(FFT(k,s),1,s)++\cdots++\operatorname{inc}(FFT(k,s),s-1,s).$$

例如：

$$FFT(1,3)=[0,1,2],$$ $$FFT(2,3)=[0,1,2,1,2,0,2,0,1],$$ $$FFT(3,3)=[0,1,2,1,2,0,2,0,1,1,2,0,2,0,1,0,1,2,2,0,1,0,1,2,1,2,0].$$

给定一个长度为 $N$ 的序列 $v$ 和一个正整数 $s$。请找出 $v$ 作为连续子序列第一次出现在

$$FFT(10^{10^{100}}+1,s)$$

中的起始位置，并输出该位置对 $10^9+7$ 取模的结果；如果 $v$ 不出现，则输出 -1。

本文中的位置从 $0$ 开始计数。

输入格式

第一行一个正整数 $T$，表示测试组数。

接下来 $T$ 组测试，每组格式如下：

第一行两个正整数 $N,s$。

第二行 $N$ 个整数，表示序列 $v$。保证每个元素都在 $[0,s-1]$ 内。

输出格式

对每组测试输出一行：

• 若 $v$ 会在 $FFT(10^{10^{100}}+1,s)$ 中出现，输出其第一次出现位置对 $10^9+7$ 取模的结果；
• 否则输出 -1。

数据范围与子任务

• $1\le s\le 1000000000$
• $1\le N\le 500000$
• $1\le T\le 500000$
• 一个输入文件中所有测试的 $N$ 之和不超过 $500000$。
• 10%：$T\le 20$，$N\le 100$，$s\le 3$
• 10%：$T\le 20$，$s\le 4$，且若答案存在，则答案不超过 $500000$
• 10%：$s\le 4$
• 30%：$s\le 5$
• 30%：$s\le N$
• 保证：若存在某个 $K$ 使得 $v$ 出现在 $FFT(K,s)$ 中，则 $v$ 也会出现在 $FFT(10^{10^{100}}+1,s)$ 中。

样例输入1

5
4 2
1 0 1 1
5 3
2 0 1 2 1
20 6
2 4 5 0 1 2 3 5 0 1 2 3 4 0 1 2 3 4 5 1
2 10000000
5 5
5 5
4 3 2 1 0

样例输出1

11
134
83
273492549
-1

样例说明

共有 $T=5$ 组测试。第一组中，$FFT(10^{10^{100}}+1,2)$ 的前若干项以

0110100110010110