给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中所有元素 $$$a_i$$$ 均位于 $$$[1, k]$$$ 范围内。有多少个不同的 $$$m$$$ 整数数组 $$$b$$$ 包含 $$$a$$$ 作为子序列,其中所有元素 $$$b_i$$$ 都在 $$$[1, k]$$$ 范围内?如果两个数组至少有一个位置不同,则认为它们不同。
如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得,则序列 $$$x$$$ 是序列 $$$y$$$ 的子序列。
由于答案可能很大,因此打印它对 $$$10^9 + 7$$$ 取模。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$n \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$) - 的大小分别是 $$$a$$$、$$$b$$$ 的大小以及数组中允许的最大值。
每个测试用例的下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots a_n$$$ ($$$1\le a_i \le k$$$) - 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 合适数组 $$$b$$$ 的数量,以 $$$10^9+7$$$ 为模。
示例
输入 #1
7 1 1000000 1 1 3 4 3 1 2 2 5 7 8 1 2 3 4 1 6 6 18 18 2 2 5 2 16 1 10 2 1 8 10 1234567 1 1 2 1 2 2 2 1 5 1000000000 1000000000 525785549 816356460 108064697 194447117 725595511
输出 #1
1 9 1079 1 1023 906241579 232432822
注意
对于第一个示例,由于 $$$k=1$$$,因此只有一个大小为 $$$m$$$ 的数组,由整数 $$$[1, k]$$$ 组成。该数组 ($$$[1, 1, \ldots, 1]$$$) 包含原始数组作为子序列,因此答案为 1。
对于第二个示例,$$$9$$$ 数组为 $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[1, 2, 2, 3]$$$、$$$[1、2、3、2]$$$、$$$[1、3、2、2]$$$、$$$[2、1、2、2]$$$、$$$[3、1、2、2]$$$。
对于第四个示例,由于 $$$m=n$$$,因此包含 $$$a$$$ 作为子序列的唯一大小为 $$$m$$$ 的数组是 $$$a$$$ 本身。