Snuke’s dictionary contains $n$ distinct words $s_1, \ldots, s_n$. Each word consists of English lowercase letters. The words are sorted lexicographically, i.e., $s_1 < \cdots < s_n$. Unfortunately, you can’t read some characters in his dictionary. You replaced those characters with ‘?’. Compute the number of ways to replace each ‘?’ with an English lowercase letter and make a valid dictionary, modulo $1\,000\,000\,007$.

Input

First line of the input contains one integer $n$ ($1 \le n \le 50$). Then $n$ lines follow, $i$’th of then contains word $s_i$ ($1 \le |s_i| \le 20$, each character in $s_i$ is an English lowercase letter or a ‘?’).

Output

Print the answer.

Examples

Input 1

2
?sum??mer
c??a??mp

Output 1

703286064

Input 2

3
snuje
????e
snule

Output 2

1