Shera decided that N matches are going to be played between them in the given order, with M distinct rackets. According to this format, both players play with the same type of racket in a match. All types of racket must be used in atleast one out of N matches. A particular type of racket may be used in more than one match.
It is known that if a player is better than his opponent with some type of racket, he will always win a match whenever the game is played with that type of racket.
Shera due to his busy schedule missed the tournament but has the results of all the matches. Instead of declaring the results, he starts calculating the number of ways in which the N matches could have been played.
Help Shera to calculate this so that the result could be declared soon.
Since, the answer may be very large. Print it modulo 109+7 .
Input Format:
First line contains an integer T , denoting the number of test cases.
The first line of each test case contains two space separated integers N and M denoting the number of matches and number of racket respectively.
N lines follow each of which will contain a string. More precisely, each line will contain the name of the player(Dev or Awtans) who wins the ith match.
Output Format:
For each test case, print the answer in a separate line.
Input Constraints:
Let the two kinds of rackets be Yonex Arcsaber and Li-ning G-force
Sample Case 1: