Dictionary

물음표가 포함된 n개의 문자열에서 물음표를 소문자로 바꾸어 결과 문자열이 사전순으로 엄격히 증가하도록 하는 경우의 수를 1,000,000,007로 나눈 나머지로 구한다.

어려움8동적 계획법문자열조합론구현아직 제출이 없습니다시간 제한4초메모리 제한512 MB

문제 설명

예제2

문제

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.