사전

시간 제한4초메모리 제한512 MB

요약

정렬된 n개의 단어에 있는 ?를 영어 소문자로 바꿔 단어들이 사전 순으로 엄격히 증가하도록 하는 방법의 수를 1,000,000,007로 나눈 나머지로 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열, 재귀
정답자: 아직 제출이 없습니다

문제

Snuke의 사전에는 서로 다른 $n$ 개의 단어 $s_1, \ldots, s_n$ 이 들어 있다. 각 단어는 영어 소문자로 이루어져 있다. 단어는 사전순으로 정렬되어 있으며, 즉 $s_1 < \cdots < s_n$ 이다. 사전의 일부 문자는 읽을 수 없어서 ?로 바뀌어 있다. 각 ?를 영어 소문자로 바꿔서 올바른 사전이 되는 방법의 수를 세어라. 답은 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 정수 $n$ ( $1 \le n \le 50$ )이 주어진다. 이어지는 $n$ 개의 줄에 단어 $s_i$ ( $1 \le |s_i| \le 20$ )가 한 줄에 하나씩 주어진다. 각 $s_i$ 의 문자는 영어 소문자이거나 ?이다.

출력

답을 출력한다.

예제2

예제 1
입력
```
2
?sum??mer
c??a??mp
```
예상 출력
```
703286064
```
예제 2
입력
```
3
snuje
????e
snule
```
예상 출력
```
1
```