Nayra doesn’t like stories of people receiving random arrays as birthday presents, but this time she received an array (A) and a number (M) as a present for her own birthday! After struggling for a day trying to figure out what to do with these numbers, she asked Aryan for help.

Aryan suggested that they should play the following game using another array B (generated using A) of size M, with Nayra going first.

In one move the player can choose one index (say i) and number X such that 1 < X ≤ B_i, and then replace B_i by ⌊B_i/X⌋. The game ends when all elements of B become 1. The player who can't move loses.

There are N^M possible B arrays that can be generated using A, by selecting B_i=A_j (1≤j≤N), independently for each 1≤i≤M. For example: A = [2, 3, 3], and M = 3, then there are total 27 arrays.

You have to count the number of B's out of the possible N^M B's such that Nayra wins. Since, this number can be large print it modulo 1000000007.

⌊X/Y⌋ denotes the floor function. Floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ A_i ≤ 10^15
• 1 ≤ M ≤ 10^15
• 1 ≤ N ≤ 10^5
• Sum of N in a testfile ≤ 2000000

Subtasks

• Subtask #1 (10 points): 1 ≤ A_i ≤ 5, 1 ≤ M ≤ 5, 1 ≤ N ≤ 5
• Subtask #2 (20 points): 1 ≤ A_i ≤ 10000, 1 ≤ M ≤ 1000, 1 ≤ N ≤ 1000, Sum of N in a testfile ≤ 20000
• Subtask #3 (70 points): Original constraints.

Input

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two integers N and M (the size of the array A and B respectively).
• The second line of each test case consists of N space-separated integers A1, A2, ... AN.

Output

• For each testcase print number of possible starting B array that are winning games for Nayra.

Sample 0

Input

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

Output

2
2
27
1024

Explanation

For the first testcase, the possible B arrays are [2] or [5], in the first turn Nayra can change them to 1 and hence win the game.
For the second testcase, the possible B arrays are [2,2] , [2,5] , [5,2] or [5,5]. For [2,2] and [5,5], Aryan can always mirror Nayra's move and win. We can show that Nayra wins if the starting configuration is [5,2], [2,5] by change 5 to 2.