goatrip-2

Chintu is a final year computer engineering student , who loves programming . All the time he is busy coding . His friends though don't like to code and 
always want to enjoy . They ask their friend Chintu to accompany them on their trip to Goa , but he refuses . They persuade him , so he agrees on one condition
, if they solve the following problem . He asks them to prepare a list of friends going to Goa maintaining the following property  , for the first k+1 friends
the name of ith friend(indexing from 0) , where  0 ≤ i < k, should be a substring of the (i+1)th friend .
Find the number of permutations of all friends which are going on the Trip . 
Since the friends are not that smart, they have asked you to solve it . Please help them .

Note: 
Since the value can be very large take modulo : 10^9 + 9.
All names are lowercase.
All the friends names are distinct. 

Input :
The first line contains T , the number of test cases .
The next line  contains n , the total number of friends and k.
The next n lines contains the names of the friends.

Constraints : 
 1 ≤ T ≤ 100
3 ≤ n ≤30 , 0 ≤ k ≤ 29
Length of each name , L is  2 ≤ L ≤ 30.

output : 
a single integer giving the number of permutations.

SAMPLE INPUT
2
3 1 
raj 
rajunder 
raju 
3  0 
rajat
kashish
piyush

SAMPLE OUTPUT
3
6

Explanation

for the first test case , since k = 1 , we have to maintain the order for only the first and the second i.e. k+1 friends , so the 
possible configurations are 

raj rajunder raju 
raj raju rajunder 
raju rajunder raj
So, output 3 

for the second case , since k = 0, therefore answer is 6 . i.e. all possible configurations.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: