B'You are given an array a of n integers, where all elements a_i lie in the range [1, k] . How many different arrays b of m integers, where all elements b_i lie in the range [1, k] , contain a as a subsequence? Two arrays are considered different if they differ in at least one position. A sequence x is a subsequence of a sequence y if x can be obtained from y by the deletion of several (possibly, zero or all) elements. Since the answer may be large, print it modulo 10^9 + 7 . The first line of the input contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains three integers n , m , k ( 1 <= n <= 2 cdot 10^5 , n <= m <= 10^9 , 1 <= k <= 10^9 ) -- the size of a , the size of b , and the maximum value allowed in the arrays, respectively. The next line of each test case contains n integers a_1, a_2, ldots a_n ( 1 <= a_i <= k ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, output a single integer -- the number of suitable arrays b , modulo 10^9+7 . For the first example, since k=1 , there is only one array of size m consisting of the integers [1, k] . This array ( [1, 1, ldots, 1] ) contains the original array as a subsequence, so the answer is 1. For the second example, the 9 arrays are [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] . For the fourth example, since m=n , the only array of size m that contains a as a subsequence is a itself. '...