Solve the programming task below in a Python markdown code block.
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