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}.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
def numDec(s):
  if not s:
   return 0

  dp = [0 for _ in range(len(s) + 1)]

  dp[0] = 1
  dp[1] = 0 if s[0] == '0' else 1


  for i in range(2, len(dp)):

   if s[i-1] != '0':
    dp[i] += dp[i-1]

   two_digit = int(s[i-2 : i])
   if two_digit >= 10 and two_digit <= 26:
    dp[i] += dp[i-2]
  return dp[len(s)]

t = int(input())

while(t):
 t-=1
 s = input()
 print(numDec(s)%1000000007)

t = int(input())
for i in range(t):
 def numDecodings(A):
  if A[0]=='0':
   return 0
  d=[0]*(len(A)+1)
  d[0]=1
  d[1]=1
  for i in range(1,len(A)):
   g=int (A[i-1]+A[i])
   if A[i]=='0' and(g!=10 and g!=20) :
    return 0
   elif g==10 or g==20 :
    d[i+1]=d[i-1]
   elif g>10 and g<=26 :
    d[i+1]=d[i]+d[i-1]
   else : 
    d[i+1]=d[i]
  
 
  return d[len(A)]%1000000007
 digits = input()
 print(numDecodings(digits))

# cook your dish here
def numDec(s):
  if not s:
   return 0

  dp = [0 for _ in range(len(s) + 1)]

  dp[0] = 1
  dp[1] = 0 if s[0] == '0' else 1


  for i in range(2, len(dp)):

   if s[i-1] != '0':
    dp[i] += dp[i-1]

   two_digit = int(s[i-2 : i])
   if two_digit >= 10 and two_digit <= 26:
    dp[i] += dp[i-2]
  return dp[len(s)]

t = int(input())

while(t):
 t-=1
 s = input()
 print(numDec(s)%1000000007)

for _ in range(int(input())):
 s = input()
 n = len(s)
 decode = [0]*(n+1)
 if s[0]=='0':
  print(0)
  continue
 
 decode[0] = 1
 decode[1] = 1
 modul = 1000000007
 for i in range(2, n+1):
  if s[i-1]>'0': 
   decode[i] = (decode[i]%modul+decode[i-1]%modul)%modul
   
  if s[i-2]=='1' or (s[i-2]=='2' and s[i-1]<'7'):
   decode[i] = (decode[i]%modul+decode[i-2]%modul)%modul
 
 print(decode[n])
 


N = 10**9 + 7 

t = int(input())
for _ in range(t):
 s = str(input())
 
 if(s[0]=='0'):
  print(0)
 else:
  x = len(s)
  a = [1]*(x+1)
  for i in range(2,x+1):
   if(s[i-1]=='0'):
    if(s[i-2]=='1' or s[i-2]=='2'):
     a[i] = a[i-2]
    else:
     a[x] = 0
     break
   elif(s[i-1]=='7' or s[i-1]=='8' or s[i-1]=='9'):
    if(s[i-2]=='1'):
     a[i] = a[i-1] + a[i-2]
    else:
     a[i] = a[i-1]
   else:
    if(s[i-2]=='1' or s[i-2]=='2'):
     a[i] = a[i-1] + a[i-2] 
    else:
     a[i] = a[i-1]
   a[i] = a[i]%N
  
  print(a[x])
  
   


def numDecodings(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)] # careful
t=int(input())
for _ in range(t):
 st=input()
 print(numDecodings(st)%1000000007)


def count_ways(s, indx, n):
 if indx == n:
  return 1

 if s[indx] == '0':
  return 0

 if dp[indx] != -1:
  return dp[indx]

 ans = count_ways(s, indx+1, n)%1000000007

 if n - indx >= 2 and (int(s[indx:indx+2]) <= 26):
  ans += count_ways(s, indx+2, n)%1000000007
  ans %= 1000000007

 dp[indx] = ans
 return ans

t = int(input())

while t:
 t -= 1

 s = input()

 dp = [-1]*len(s)

 print(count_ways(s, 0, len(s)))

def count_ways(s, indx, n):
 if indx == n:
  return 1

 if s[indx] == '0':
  return 0

 if dp[indx] != -1:
  return dp[indx]

 ans = count_ways(s, indx+1, n)%1000000007

 if n - indx >= 2 and (int(s[indx:indx+2]) <= 26):
  ans += count_ways(s, indx+2, n)%1000000007
  ans %= 1000000007

 dp[indx] = ans
 return ans

t = int(input())

while t:
 t -= 1

 s = input()

 dp = [-1]*len(s)

 print(count_ways(s, 0, len(s)))

def numDecodings(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)]
for _ in range(int(input())):
 s = input();
 print(numDecodings(s)%1000000007)


for _ in range(int(input())):
 s = input()
 n = len(s)
 dp = [0 for _ in range(n)]
 if s[0] != '0':
  dp[0] = 1
 for i in range(1, n):
  x = int(s[i])
  y = int(s[i-1:i+1])
  if x >= 1 and x <= 9:
   dp[i] += dp[i-1]
  if y >= 10 and y <= 26:
   if i - 2 >= 0:
    dp[i] += dp[i-2]
   else:
    dp[i] += 1
 print(dp[-1] % 1000000007)


# cook your dish here
t = int(input())
for _ in range(t):
 s = input()
 dp = [0] * (len(s)+1)
 dp[0] = 1
 dp[1] = 1
 for i in range(2,len(s)+1):
  if s[i-1] >'0':
   dp[i] = dp[i-1]
  if s[i-2] == '1' or (s[i-2] == '2' and s[i-1] < '7'):
   dp[i] += dp[i-2]
 
 if s[0] == '0':
  print(0)
 else:
  print(dp[len(s)] % (10**9 + 7))

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)