Alice likes prime numbers. According to Alice, only those strings are nice whose sum of character values at a prime position is prime. She has a string $S$. Now, she has to count the number of nice strings which come before string $S$( including $S$) in the dictionary and are of the same length as $S$. 
Strings are zero-indexed from left to right.
To find the character value she uses the mapping {'a': 0, 'b':1, 'c':2 ……. 'y': 24, 'z':25} .
For example, for string $abcde$ Characters at prime positions are $'c'$ and $'d'$. c + d = 2 + 3 = 5. Since, 5 is a prime number, the string is $nice$.
Since there could be many nice strings print the answer modulo $10^{9}+7$.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, the string $S$. 

-----Output:-----
For each testcase, output in a single line number of nice strings modulo $10^{9}+7$.

-----Constraints-----
- $1 \leq T \leq 10$
- $2 \leq |S| \leq 10^2$
String $S$ contains only lowercase letters.

-----Sample Input:-----
1
abc

-----Sample Output:-----
10

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import defaultdict
from copy import copy

MOD = 10**9 + 7

R = lambda t = int: t(input())
RL = lambda t = int: [t(x) for x in input().split()]
RLL = lambda n, t = int: [RL(t) for _ in range(n)]

# primes up to n
def primes(n):
  P = []
  n = int(n)
  U = [1] * (n+1)
  p = 2
  while p <= n:
    if U[p]:
      P += [p]
      x = p
      while x <= n:
        U[x] = 0
        x += p
    p += 1
  return P
  
    
  
def solve():
    S = R(str).strip()
    X = [ord(c)-ord('a') for c in S]
    P = primes(10000)
    L = defaultdict(lambda : 0)
    s = 0
    for i in range(len(S)):
        p = i in P
        NL = defaultdict(lambda : 0)
        for a in range(26):
            for l in L:
                NL[l + a * p] += L[l]
        for a in range(X[i]):
            NL[s + a * p] += 1
        s += X[i] * p
        L = NL
    L[s] += 1
    r = 0 
    for p in P:
        r += L[p]
    print(r % MOD)
    
T = R()
for t in range(1, T + 1):
    solve()