We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Hyper Strings

Hyper Strings

String is called a Super String if and only if:

  • contains only letters ;
  • For any and , has lower ascii code than , where

Given a set of Super Strings , a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set . We can use each Super String as many times as we want.

Given set , you have to compute the number of Hyper Strings with length no greater than .

Input Format

The first line of input contains two integers, (the number of Super Strings in ) and . The next lines describe the Super Strings in set .

Constraints

and are not greater than .

Output Format

Output an integer which is the number of possible Hyper Strings that can be derived. Since it may not fit in bit integer, print the output module . (i.e. answer = answer % )

Sample Input

2 3  
a  
ab

Sample Output

7

Explanation

In the example all the Hyper Strings are : "" (empty string), "", "", "", "", "", and "".