Dhruvil has always been a studious person and will be completing his Engineering soon. He is always kneen about solving problems and is preparing hard for his next interview at Hackerrank. He has practiced lots of problems and now he came across this problem.
Given a message containing English letters(A-Z), it is being encoded to numbers using the following mapping:
'A' -> 1,'B' -> 2 ……………… 'Z' -> 26.
Now, given a non-empty string containing only digits, help Dhruvil determine the total number of ways to decode it.
While decoding you need to choose a substring of charachters and not a subsequence. Also a chosen substring should not contain any leading "0"s, but can contain trailing "0"s. Since the output can be very large print the answer as modulo 10^9 + 7 i.e 1000000007.
-----Input:-----
The first line of the input consists of single integer T, the number of test cases.
Each test case consists of a string.
-----Output:-----
For each test case print a single integer - the total number of ways to decode the digit string.
-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq S \leq 10^9$
-----Sample Input:-----
2
12
226
-----Sample Output:-----
2
3
-----EXPLANATION:-----
There are 2 possible ways. It could be decoded as "AB" {1,2} or "L" {12}.
There are 3 possible ways. It could be decoded as "BZ" {2,26}, "VF" {22,6}, or "BBF" {2,2,6}.
import sys
import math
import bisect
from sys import stdin,stdout
from math import gcd,floor,sqrt,log
from collections import defaultdict as dd
from bisect import bisect_left as bl,bisect_right as br

sys.setrecursionlimit(100000000)

ii =lambda: int(input())
si =lambda: input()
jn =lambda x,l: x.join(map(str,l))
sl =lambda: list(map(str,input().strip()))
mi =lambda: list(map(int,input().split()))
mif =lambda: list(map(float,input().split()))
lii =lambda: list(map(int,input().split()))

ceil =lambda x: int(x) if(x==int(x)) else int(x)+1
ceildiv=lambda x,d: x//d if(x%d==0) else x//d+1

flush =lambda: stdout.flush()
stdstr =lambda: stdin.readline()
stdint =lambda: int(stdin.readline())
stdpr =lambda x: stdout.write(str(x))

mod=1000000007
def sol(s):  
 dp = [0] * (len(s) + 2)
 dp[0] = 1
  
 for i in range(len(s)):
  if int(s[i]) != 0:
   dp[i+1] += dp[i]
   
  if int(s[i:i+2]) >= 10 and int(s[i:i+2]) <= 26:
   dp[i+2] += dp[i]
  
 return dp[len(s)] 
 


#main code
for _ in range(ii()):
 s=si()
 ans=sol(s)
 print(ans%mod)

import sys
import math
import bisect
from sys import stdin,stdout
from math import gcd,floor,sqrt,log
from collections import defaultdict as dd
from bisect import bisect_left as bl,bisect_right as br

sys.setrecursionlimit(100000000)

ii =lambda: int(input())
si =lambda: input()
jn =lambda x,l: x.join(map(str,l))
sl =lambda: list(map(str,input().strip()))
mi =lambda: list(map(int,input().split()))
mif =lambda: list(map(float,input().split()))
lii =lambda: list(map(int,input().split()))

ceil =lambda x: int(x) if(x==int(x)) else int(x)+1
ceildiv=lambda x,d: x//d if(x%d==0) else x//d+1

flush =lambda: stdout.flush()
stdstr =lambda: stdin.readline()
stdint =lambda: int(stdin.readline())
stdpr =lambda x: stdout.write(str(x))

mod=1000000007
def sol(s):  
 dp = [0] * (len(s) + 2)
 dp[0] = 1
  
 for i in range(len(s)):
  if int(s[i]) != 0:
   dp[i+1] += dp[i]
   
  if int(s[i:i+2]) >= 10 and int(s[i:i+2]) <= 26:
   dp[i+2] += dp[i]
  
 return dp[len(s)] 
 


#main code
for _ in range(ii()):
 s=si()
 ans=sol(s)
 print(ans%mod)
