16838번 - Dictionary 다국어

문제

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

입력

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

출력

Print the answer.

제한

힌트