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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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))


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]
			elif 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)]
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)))


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)


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)]
for _ in range(ii()):
	s = si()
	ans = sol(s)
	print(ans % mod)