시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Snuke’s dictionary contains n distinct words s1, . . . , sn. Each word consists of English lowercase letters. The words are sorted lexicographically, i.e., s1 < · · · < sn. 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.

입력

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

출력

Print the answer.

예제 입력 1

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

예제 출력 1

703286064

예제 입력 2

3
snuje
????e
snule

예제 출력 2

1