Dictionary

Time limit4sMemory limit512 MB

Summary

Count the ways to replace each ? in n sorted words with lowercase letters so the words stay in strictly increasing lexicographic order, modulo 1,000,000,007.

Level: Medium6 of 10
Topics: Dynamic programming, String, Recursion
Solved: No attempts yet

Problem

Snuke's dictionary contains $n$ distinct words $s_1, \ldots, s_n$ . Each word consists of English lowercase letters. The words are sorted lexicographically, that is, $s_1 < \cdots < s_n$ . Some characters in the dictionary are unreadable, so they were replaced with ?. Count the ways to replace each ? with an English lowercase letter so that the result is a valid dictionary. Print the count modulo 1,000,000,007.

Input

The first line contains an integer $n$ ( $1 \le n \le 50$ ). Each of the next $n$ lines contains a word $s_i$ ( $1 \le |s_i| \le 20$ ). Each character of $s_i$ is either an English lowercase letter or ?.

Output

Print the answer.

Examples2

Example 1
Input
```
2
?sum??mer
c??a??mp
```
Expected output
```
703286064
```
Example 2
Input
```
3
snuje
????e
snule
```
Expected output
```
1
```