As we all know the fact, you can use several Source Words to compose an Interesting Word. Little Gyro has already learnt this fantastic idea from one of his best friends Brother Yu.
On Little Gryo's birthday, fortunately, Little Gryo received a gift from Brother Yu. The gift consists of n Interesting Words . Little Gyro also thought those words were really fantastic. So he decided to play with these words.
For each Interesting Word , Little Gyro will select a period of consecutive letters , and splice into a new word T within the given order, and then he defined these kind of words "Fascinating Words". It means you can take apart a Fascinating Word T and form n period of consecutive letters from the given Interesting Words. Specially, if Little Gyro considers the Interesting Word really useless, he'll not choose any letter from this Interesting Word either.
For example, supposed that there are some Interesting Words: "telephone", "microscope". Little Gyro may select a period of consecutive letters from each given word such as: "tele", "scope". And then form the Fascinating Word "telescope". Specially, Little Gyro also can only select "scope" and form the Fascinating Word "scope", if he dislikes the first Interesting Word.
Now given all the Interesting Words that Little Gyro has received on his birthday, Little Gyro wants to know the total number of the different Fascinating Words that he can generate.

Each input file only contains one test case.
The first line contains an integer n (1 ≤ n ≤ 2000), indicating the number of the Interesting Words.
Then, the following n lines, each line contains an Interesting Word  (1 ≤  ≤ 5×).
It's guaranteed that the Interesting Words can only be made up by the lowercase letters, and the sum of the length of the Interesting Words  of all test cases will not exceed 5×.

For each test case, output the number of the different Fascinating Words that Little Gyro can generate.
Because the number may be very large, just output the number mod .

2
aa
ab

8

3
abb
aca
aba

139

For the first sample, Little Gyro can generate 8 different Fascinating Words in total, including "a", "b", "aa", "ab", "aaa", "aab", "aaab" and the empty word.