What Does UNIST Stand For?

Time limit1sMemory limit512 MB

Summary

Count ways to pick a prefix of each of N words so the concatenation spells UNIST, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, String, Hash map, Recursion
Solved: No attempts yet

Problem

UNIST stands for Ulsan National Institute of Science and Technology. One day, Woni wondered whether there are other words whose acronym is UNIST.

Let $\operatorname{len}(a)$ denote the length of a word $a$ . Given $N$ words $W_1, W_2, \dots, W_N$ , for each word $W_i$ $(1 \le i \le N)$ , let $P_i$ be a string obtained by taking between 0 and $\operatorname{len}(W_i)$ characters from the front of $W_i$ . In other words, $P_i$ is a prefix of $W_i$ of length $\operatorname{len}(P_i)$ .

Find the number of ways to choose $P_i$ $(1 \le i \le N)$ such that $P_1+P_2+\dots+P_N$ is UNIST. Here, the operation $+$ is string concatenation.

Input

The first line gives the number of words $N$ .

The next $N$ lines give the $N$ words $W_1, W_2, \dots, W_N$ , one per line.

Each $W_i$ $(1 \le i \le N)$ is a string consisting of one or more uppercase English letters.

Output

Print the number of ways to choose $P_1, P_2, \dots, P_N$ such that $P_1+P_2+\dots+P_N$ is UNIST, modulo 1,000,000,007.

Constraints

$1 \le N \le 100,000$
$\operatorname{len}(W_i) \le 25$

Examples3

Example 1

Input

7
ULSAN
NATIONAL
INSTITUTE
OF
SCIENCE
AND
TECHNOLOGY

Expected output

Example 2
Input
```
5
UNICODE
IS
THE
SPORTS
TIME
```
Expected output
```
4
```
Example 3
Input
```
2
UNIS
UT
```
Expected output
```
0
```