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.
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.
