Counting Games

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Henry and Derek are waiting in a room. They have successfully qualified for the Snackdown Finals 2016, and decide to pass the time by playing a new game.
Before the game starts, they select N numbers: v(0), v(1), ..., v(N1). These numbers will stay fixed throughout the game.
The initial state of the game consists of K integers x_{1}, x_{2}, ..., x_{K}, each of which is in the range [0, N1]. Thus, there are N^{K} distinct states all in all. Then the players take turns, starting with Henry. In a turn, a player selects one of the integers, say x_{i}, and decreases it by some positive multiple of 2^{v(xi)}. However, this is only valid if the resulting number is nonnegative. A player loses if there are no more valid moves left.
Henry and Derek have gotten really good at playing this game, so much that they have figured out the optimal strategy, and they always play optimally! This made the game really boring for them, because the winner is solely determined by the initial state of the game. So instead of playing the game, they decided to just answer the following question instead:
Of all the N^{K} possible initial states, how many of them result in a win for Henry?
Input
The first line of the input contains an 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 K.
The second line contains N spaceseparated integers v(0), v(1), ..., v(N1).
Output
For each test case, output a single line containing a single integer, the number of initial states that result in a win for Henry. This number can be very large, so output it modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 3
 1 ≤ K ≤ 10^{6}
 1 ≤ N ≤ 10^{5}
 0 ≤ v(i) ≤ 10^{4}
Example
Input: 3 2 3 1 0 5 3 2 0 1 0 0 5 3 2 0 1 0 1 Output: 4 94 100
Explanation
In the first case, the following initial states result in a win for Henry: [1,1,1], [0,0,1], [0,1,0], [1,0,0].
Author:  kevinsogo 
Tags  kevinsogo 
Date Added:  2072016 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 