Dictionary

Sunuke-kun's dictionary contains the words s1, ..., sn, which consist of n lowercase letters. This satisfies s1 <... <sn when compared in lexicographical order. Unfortunately, some characters are faint and unreadable. Unreadable characters are represented by?. Find out how many ways to restore the dictionary by replacing? With lowercase letters, even with mod 1,000,000,007.

Constraints

• 1 ≤ n ≤ 50
• 1 ≤ | si | ≤ 20
• The characters that appear in si are lowercase letters or?

Input

n s1 .. .. sn

Output

Print the answer on one line.

Examples

Input

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

Output

703286064

Input

3 snuje ????e snule

Output

1

inputFormat

Input

n s1 .. .. sn

outputFormat

Output

Print the answer on one line.

Examples

Input

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

Output

703286064

Input

3 snuje ????e snule

Output

1

样例

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

703286064