using p:

import sys MOD = 10**9 + 7

--- suffix array (doubling) and LCP (Kasai) ---

def build_sa(s):

n = len(s)
k = 1
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0]*n
# we will use tuple sort; for n up to 1e5 this is OK in Python
while True:
    sa.sort(key=lambda i: (rank[i], rank[i+k] if i+k < n else -1))
    tmp[sa[0]] = 0
    for i in range(1, n):
        prev, cur = sa[i-1], sa[i]
        left = (rank[prev], rank[prev+k] if prev+k<n else -1)
        right= (rank[cur],  rank[cur+k]  if cur+k<n else -1)
        tmp[cur] = tmp[prev] + (1 if left != right else 0)
    rank, tmp = tmp, rank
    if rank[sa[-1]] == n-1:
        break
    k <<= 1
return sa

def build_lcp(s, sa): n = len(s) rank = [0]*n for i, p in enumerate(sa): rank[p]=i lcp = [0]*n h = 0 for i in range(n): if rank[i] == 0: continue j = sa[rank[i]-1] while i+h < n and j+h < n and s[i+h]==s[j+h]: h+=1 lcp[rank[i]] = h if h: h-=1 return lcp

--- main solver per test string ---

def solve_one(s, powprefix): n = len(s) if n == 0: return 0 sa = build_sa(s) lcp = build_lcp(s, sa)

# Precompute for each start index i the sorted thresholds where distinct count grows
# process lastpos from right to left
lastpos = [-1]*26
thresholds = [None]*n  # thresholds[i] = sorted list of lengths at which new distinct letters appear for substrings starting at i
for i in range(n-1, -1, -1):
    lastpos[ord(s[i]) - 97] = i
    T = []
    for c in range(26):
        p = lastpos[c]
        if p != -1:
            T.append(p - i + 1)  # length needed to include this char
    T.sort()
    thresholds[i] = T

ans = 0
# For each suffix in SA order, add contributions for new lengths
for idx in range(n):
    start = sa[idx]
    newL = lcp[idx] + 1
    maxL = n - start
    if newL > maxL: 
        continue
    T = thresholds[start]
    # T is sorted ascending thresholds; for j in range(len(T)):
    # D for lengths in [T[j], T[j+1]-1] is (j+1)
    # last interval ends at maxL for this suffix
    m = len(T)
    # iterate intervals
    for j in range(m):
        segL = T[j]
        segR = (T[j+1]-1) if j+1 < m else maxL
        # intersection with [newL, maxL]
        L = max(newL, segL)
        R = min(maxL, segR)
        if L <= R:
            k = j+1  # distinct count
            # sum_{t=L..R} t^k = powprefix[k][R] - powprefix[k][L-1]
            ssum = (powprefix[k][R] - (powprefix[k][L-1] if L-1 >= 0 else 0)) % MOD
            ans = (ans + ssum) % MOD
    # done this suffix
return ans

--- precompute power prefix sums up to global maximum n across all tests ---

def main(): data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) strs = data[1:] maxn = 0 for s in strs: if len(s) > maxn: maxn = len(s) # distinct count at most 26 => we need powers k in [1..26] MAXK = 26 # powprefix[k][i] = sum_{x=1..i} x^k mod # We'll index powprefix[k] as list length maxn+1 with powprefix[k][0]=0 powprefix = [[0]*(maxn+1) for _ in range(MAXK+1)] for k in range(1, MAXK+1): acc = 0 for x in range(1, maxn+1): acc = (acc + pow(x, k, MOD)) % MOD powprefix[k][x] = acc

out = []
idx = 0
for s in strs:
    ans = solve_one(s, powprefix)
    out.append(str(ans))
sys.stdout.write("\n".join(out))

if name == "main": main()