题目描述
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.
输入格式
见题面
输出格式
见题面