Vincoder was cleaning his room and he found a sheet of paper. It had a string S of length N Each character siof string S had some sequence of characters Ci associated with it.
Note that string S had distinct lowercase alphabetic characters and the sequence of characters associated with each character si of string S are also part of string S.
Vincoder kept on thinking about this string and found an algorithm to generate some new strings of any desired length from this string S and the associated sequences of each character.
The algorithm is:
- Start from any character si of string S i.e new_string = si
- Now only the character from associated sequence of si is allowed to be added to new string. Let say associated sequence of si is [x,y,z] then any one of x ,y ,z can be added further. i.e new_string can be si+x OR si+y OR si+z
- Let’s say we added x in previous step. So, Let new_string =si+x. Now only the character from associated sequence of x is allowed to be added to new string. Let say associated sequence of x is [a,b,c] then new_string can be si+x+a OR si+x+b OR si+x+c
- Similarly continue further until the desired length of new_string is reached.
Vincoder wants to count the total number of non empty subsequences of all possible K length strings that can be made by using following the above algorithm.
Since he is busy with his interview prep, he wants your help in this one so that he can move forward.
Note that the answer can be large so output it modulo 109+9.
Input format
- First line conatins N
- Second line contains string S of length N
- N lines follow, ith line contains sequence of characters Ci associated with character si of string S
- Last line contains K.
Ouput format
- Total number of non-empty subsequences of all the possible K length strings modulo 109+9
Constraints
- 1<=N<=10
- 1<=length(Ci)<=N
- 1<=K<=2∗105
for s[0]=’a’ sequence of characters C0 is [b]
for s[1]=’b’ sequence of characters C1 is [a,c]
for s[2]=’c’ sequence of characters C3 is [a,b,d]
for s[3]=’d’ sequence of characters C4 is [a,d]
Strings starting from ‘a’ of length K=3 that can be formed are,
aba and abc.
Non empty subsequences of aba = [a,b,a,ab,aa,ba,aba] , 7 subsequences
Non empty subsequences of abc = [a,b,c,ab,ac,bc,abc], 7 subsequences
So total subsequences for strings starting with ‘a’ and having length = 3 are 14.
Strings starting from ‘d’ of length K=3 that can be formed are,
dda ,ddd and dab
Non empty subsequences of dda= [d,d,a,dd,da,da,dda] , 7 subsequences
Non empty subsequences of dab= [d,a,b,da,db,ab,dab], 7 subsequences
Non empty subsequences of ddd= [d,d,d,dd,dd,dd,ddd], 7 subsequences
and so on..... for b and c
To get 98 we need to add total subseqences for strings starting with ‘b’, ‘c’ similarly.
