p01742 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
```python
# seishin.py
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    MOD = 10**9 + 7
    N = int(readline())
    M = 20
    L = 26
    ca = ord('a')
    cq = ord('?')
    S = [[ca-1]*M for i in range(N)]
    for i in range(N):
        s = readline().strip()
        S[i][:len(s)] = map(ord, s)

    memo = [[[[-1]*(L+2) for i in range(M+1)] for j in range(N+1)] for k in range(N+1)]
    for i in range(N+1):
        for p in range(M+1):
            for c in range(L+2):
                memo[i][i][p][c] = 1
    for i in range(N+1):
        for j in range(i+1, N+1):
            for p in range(M+1):
                memo[i][j][p][L+1] = 0
            for c in range(L+2):
                memo[i][j][M][c] = (i+1 == j)

    def dfs(l, r, p, c):
        if memo[l][r][p][c] != -1:
            return memo[l][r][p][c]
        res = dfs(l, r, p, c+1)
        for i in range(l+1, r+1):
            if (S[i-1][p] != ca + c - 1) if S[i-1][p] != cq else (c == 0):
                break
            res += dfs(l, i, p+1, 0) * dfs(i, r, p, c+1) % MOD
        memo[l][r][p][c] = res = res % MOD
        return res
    write("%d\n" % dfs(0, N, 0, 0))
solve()

```