Scar Prepares an Attack

Time limit2sMemory limit1024 MB

Summary

Count the ways to pick a nonempty subsequence of each hyena's genotype so that each chosen birth genotype is stronger than the next, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, String, Bit manipulation, Sorting
Solved: No attempts yet

Problem

Scar is preparing an army of hyenas for an attack. $n$ hyenas came to the selection. Scar wants to pick the most capable ones, those born with a natural talent.

Each hyena has a genotype, which is a sequence of genes. Genes are denoted by lowercase Latin letters.

Each hyena's genotype at birth was some nonempty subsequence of its current genotype. During its life, an arbitrary number of arbitrary genes were inserted at various places in the genotype, and it took its current form.

We say genotype $a$ is stronger than genotype $b$ if there is an index $i$ such that $a_j = b_j$ for all $j < i$ and $a_i$ comes earlier in the alphabet than $b_i$ . If $a_i = b_i$ for all $i$ , the genotype with fewer genes is stronger.

Scar wonders what the birth genotypes could have been. It is known that the birth genotype of the $i$ -th hyena was stronger than the birth genotype of the $(i+1)$ -th hyena. Count the number of possible sets of birth genotypes that satisfy all these conditions, modulo $1\,000\,000\,007$ .

Input

The first line contains $n$ ( $1 \le n \le 10$ ), the number of hyenas. Each of the next $n$ lines contains the current genotype $s_i$ of the $i$ -th hyena. Each string has length at most 13.

Output

Print the number of sets of birth genotypes that satisfy all conditions, modulo $1\,000\,000\,007$ .

Examples3

Example 1
Input
```
2
aaa
aa
```
Expected output
```
1
```
Example 2
Input
```
2
ab 
abc
```
Expected output
```
13
```
Example 3
Input
```
3
qwerty
qwerty
ytrewq
```
Expected output
```
87506
```