A top secret message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
You are an FBI agent. You have to determine the total number of ways that message can be decoded, as the answer can be large return the answer modulo 10^{9} + 7.
Note: An empty digit sequence is considered to have one decoding. It may be assumed that the input contains valid digits from 0 to 9 and If there are leading 0s, extra trailing 0s and two or more consecutive 0s then it is an invalid string.
Example 1:
Input: str = "123"
Output: 3
Explanation: "123" can be decoded as "ABC"(123),
"LC"(12 3) and "AW"(1 23).
Example 2:
Input: str = "90"
Output: 0
Explanation: "90" cannot be decoded as it's an invalid string and we cannot decode '0'.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function CountWays() which takes the string as str as input parameter and returns the total number of ways the string can be decoded modulo 10^{9} + 7.
 
Expected Time Complexity: O(n)
Expected Space Complexity: O(n) where n  = |str|
Constraints:
1 <= |str| <= 10^{4}

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n) where n  = |str|

Starter code:
#User function Template for python3



class Solution:

	def CountWays(self, str):

		# Code here

Solutions:
class Solution:

	def CountWays(self, st):
		di = {x: 1 for x in range(1, 27)}
		m = 1000000007
		li = [1]
		if st[0] == '0':
			return 0
		li.append(1)
		for i in range(1, len(st)):
			if st[i] == '0':
				if st[i - 1] == '1' or st[i - 1] == '2':
					x = li[-2] % m
					li.append(x)
				else:
					return 0
			else:
				x = int(str[i])
				y = int(str[i - 1:i + 1])
				if y == x or y not in di.keys():
					n = li[-1] % m
					li.append(n)
				else:
					li.append((li[-1] % m + li[-2] % m) % m)
		return li[-1] % m


class Solution:

	def CountWays(self, str):
		s = str
		mod = 10 ** 9 + 7
		dp = {len(s): 1}
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '0':
				dp[i] = 0
			else:
				dp[i] = dp[i + 1]
			if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] in '0123456')):
				dp[i] += dp[i + 2]
		return dp[0] % mod


class Solution:

	def CountWays(self, str):
		t = [-1 for i in range(len(str) + 1)]
		mod = 10 ** 9 + 7

		def helper(idx, str, t):
			if idx == len(str):
				return 1
			if str[idx] == '0':
				return 0
			if t[idx] != -1:
				return t[idx]
			res = helper(idx + 1, str, t)
			if idx < len(str) - 1 and (str[idx] == '1' or (str[idx] == '2' and str[idx + 1] < '7')):
				res = res + helper(idx + 2, str, t)
			t[idx] = res
			return t[idx] % mod
		return 0 if len(str) == 0 else helper(0, str, t) % mod


class Solution:

	def CountWays(self, s):

		def dfs(i, n):
			nonlocal d
			if i in d:
				return d[i]
			if s[i] == '0':
				return 0
			res = 0
			res = (res + dfs(i + 1, n)) % (10 ** 9 + 7)
			if i + 1 < n and (s[i] == '1' or (s[i] == '2' and s[i + 1] in '0123456')):
				res = (res + dfs(i + 2, n)) % (10 ** 9 + 7)
			d[i] = res % (10 ** 9 + 7)
			return res % (10 ** 9 + 7)
		n = len(s)
		d = {n: 1}
		return dfs(0, n)


class Solution:

	def CountWays(self, str):
		s = str
		n = len(s)
		h = {-1: 1, 0: 1}
		div = 10 ** 9 + 7
		if s[0] == 0:
			return 0
		for i in range(1, n):
			if s[i] == '0':
				if s[i - 1] == '0':
					return 0
				h[i] = h[i - 2] * int(int(s[i - 1] + s[i]) <= 26) % div
			elif s[i - 1] == '0':
				h[i] = h[i - 1]
			else:
				h[i] = (h[i - 1] + h[i - 2] * int(int(s[i - 1] + s[i]) <= 26)) % div
		return h[n - 1]


class Solution:

	def solve(self, data, n, dp):
		if n == 0:
			return 1
		if n == 1:
			return 1
		if dp[n] != -1:
			return dp[n]
		a = 0
		if n >= 2:
			if data[n - 2] == '1' or (data[n - 2] == '2' and data[n - 1] <= '6'):
				a += self.solve(data, n - 2, dp)
		if n >= 1 and int(data[n - 1]) != 0:
			a += self.solve(data, n - 1, dp)
		dp[n] = a
		return dp[n]

	def CountWays(self, str):
		dp = [-1 for i in range(len(str) + 1)]
		res = self.solve(str, len(str), dp)
		return res % 1000000007


class Solution:

	def CountWays(self, s):
		if not s:
			return 1
		n = len(s)
		self.s = s
		self.cache = [None] * (n + 1)
		self.cache[n - 1:] = (int(s[-1] != '0'), 1)
		return self.DP(0)

	def DP(self, j):
		if self.cache[j]:
			return self.cache[j]
		if self.s[j] == '0':
			return 0
		takeOne = self.DP(j + 1)
		twoDigit = int(self.s[j:j + 2])
		takeTwo = 0
		if twoDigit < 27:
			takeTwo = self.DP(j + 2)
		self.cache[j] = (takeOne + takeTwo) % 1000000007
		return self.cache[j]


class Solution:

	def CountWays(self, str):
		mp = {}
		return self.countWaysHelper(str, 0, mp) % (10 ** 9 + 7)

	def countWaysHelper(self, str, i, mp):
		if i == len(str):
			return 1
		if str[i] == '0':
			return 0
		if i == len(str) - 1:
			return 1
		if i in mp:
			return mp[i]
		if str[i] == '1' or (str[i] == '2' and str[i + 1] >= '0' and (str[i + 1] <= '6')):
			res = self.countWaysHelper(str, i + 1, mp) + self.countWaysHelper(str, i + 2, mp)
		else:
			res = self.countWaysHelper(str, i + 1, mp)
		mp[i] = res
		return res


class Solution:

	def CountWays(self, str):
		n = len(str)
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1 if str[0] != '0' else 0
		for i in range(2, n + 1):
			if str[i - 1] != '0':
				dp[i] += dp[i - 1]
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] <= '6'):
				dp[i] += dp[i - 2]
			dp[i] %= 10 ** 9 + 7
		return dp[n]


class Solution:

	def CountWays(self, str):
		memo = {x: -1 for x in range(len(str) + 1)}
		mod = 1000000007
		if str[0] == '0':
			return 0

		def dp(i):
			if i == 1 or i == 0:
				return 1
			if memo[i] != -1:
				return memo[i]
			count = 0
			if str[i - 1] >= '1':
				count = count + dp(i - 1) % mod
			if '1' == str[i - 2] or (str[i - 2] == '2' and str[i - 1] <= '6'):
				count = (count + dp(i - 2) % mod) % mod
			memo[i] = count
			return memo[i]
		return dp(len(str))


class Solution:

	def CountWays(self, str):
		n = len(str)
		t = [0 for i in range(n + 1)]
		if str[0] == '0':
			return 0
		t[0] = 1
		t[1] = 1
		mod = 10 ** 9 + 7
		for i in range(1, n):
			if str[i] > '0':
				t[i + 1] = t[i]
			if str[i - 1] == '1' or (str[i - 1] == '2' and int(str[i]) < 7):
				t[i + 1] += t[i - 1]
			elif str[i] == '0':
				return 0
			t[i + 1] %= mod
		return t[n]


class Solution:

	def CountWays(self, s):
		n = len(s)
		if n == 0:
			return 1
		if n == 1:
			return 0 if s[0] == '0' else 1
		dp = [0 for i in range(n)]
		dp[0] = 1
		dp[1] = 1
		if int(s[0] + s[1]) <= 26:
			dp[1] += 1
		mod = 10 ** 9 + 7
		for i in range(2, n):
			dp[i] = dp[i - 1] if s[i] != '0' else 0
			if int(s[i - 1] + s[i]) <= 26 and s[i - 1] != '0':
				dp[i] += dp[i - 2]
			dp[i] %= mod
		return dp[n - 1]


class Solution:

	def CountWays(self, s):
		if len(s) == 1 and s == '0':
			return 0
		elif len(s) == 1 and s != '0':
			return 1
		temp = {}
		for i in range(1, 27):
			temp['{}'.format(i)] = True
		memo = {}

		def check(first, second):
			if second != '':
				if first + '#' + second in memo:
					return memo[first + '#' + second]
				if not second in temp:
					return 0
				if second in temp and len(first) <= 1:
					if first == '':
						return 1
					elif first in temp:
						return 1
					else:
						return 0
			val_1 = check(first[:len(first) - 2], first[len(first) - 2:])
			val_2 = check(first[:len(first) - 1], first[len(first) - 1:])
			memo[first + '#' + second] = val_1 + val_2
			return val_1 + val_2
		return check(s, '') % (10 ** 9 + 7)


class Solution:

	def CountWays(self, stg):
		dp = [-1 for i in range(len(stg) + 1)]
		n = len(stg)

		def recursive(dp, stg, n):
			if n == 0:
				return 1
			if dp[n] != -1:
				return dp[n]
			char = stg[n - 1]
			if char == '0' and (n == 1 or int(stg[n - 2]) < 1 or int(stg[n - 2]) > 2):
				return float('inf')
			if char != '0':
				dp[n] = recursive(dp, stg, n - 1)
				if n > 1 and (char <= '9' and stg[n - 2] == '1' or (char <= '6' and stg[n - 2] == '2')):
					dp[n] += recursive(dp, stg, n - 2)
			else:
				dp[n] = recursive(dp, stg, n - 2)
			return dp[n]
		ans = recursive(dp, stg, n)
		if ans == float('inf'):
			return 0
		return ans % 1000000007


from collections import defaultdict

class Solution:

	def s(self):
		return -1

	def CountWays(self, st):
		if st == ' ':
			return 1
		if '00' in st or st[0] == '0':
			return 0
		dic = defaultdict(self.s)
		for (key, val) in zip(range(1, 27), range(65, 91)):
			dic['{}'.format(key)] = val
		dp = [0] * (len(st) + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(1, len(st)):
			if st[i] != '0':
				dp[i + 1] = dp[i]
			if dic[st[i - 1] + st[i]] != -1:
				dp[i + 1] += dp[i - 1]
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def helper(self, str, dp):
		if str in dp:
			return dp[str]
		if len(str) <= 1:
			return 1
		mod = 1000000007
		dp[str] = 0
		if str[0] == '1' or (str[0] == '2' and len(str) > 1 and (str[1] >= '0') and (str[1] <= '6')):
			if len(str) == 2:
				dp[str] += 1
			elif str[2] != '0':
				dp[str] += self.helper(str[2:], dp) % mod
		if len(str) > 1 and str[1] != '0' or len(str) == 1:
			dp[str] = (dp[str] + self.helper(str[1:], dp)) % mod
		return dp[str]

	def CountWays(self, str):
		for i in range(len(str)):
			if str[i] == '0' and (i > 0 and str[i - 1] == '0' or str[i - 1] > '2'):
				return 0
		dp = {}
		return self.helper(str, dp)


class Solution:

	def CountWays(self, str):

		def helper(str, k, memo):
			if k == 0:
				return 1
			s = len(str) - k
			if str[s] == '0':
				return 0
			if memo[k] != None:
				return memo[k]
			res = helper(str, k - 1, memo)
			if k >= 2 and int(str[s:s + 2]) <= 26:
				res += helper(str, k - 2, memo)
			memo[k] = res
			return memo[k]
		memo = [None] * (len(str) + 1)
		return helper(str, len(str), memo) % (10 ** 9 + 7)


class Solution:

	def isValid(self, s, n):
		if s[0] == '0':
			return True
		for i in range(n - 1):
			if s[i] == s[i + 1] == '0':
				return True
		return False

	def CountWays(self, s):
		mod = 1000000000.0 + 7
		n = len(s)
		flag = self.isValid(s, n)
		if flag:
			return 0
		dp = [0] * (n + 1)
		dp[0] = dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = 0
			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] = int((dp[i] + dp[i - 2]) % mod)
		return dp[n]


class Solution:

	def __init__(self):
		self.modulo = 1000000000.0 + 7

	def checkString(self, str, start_index, cache):
		if start_index >= len(str):
			return 1
		if cache[start_index] != -1:
			return cache[start_index]
		else:
			(one_check, two_check) = (0, 0)
			if str[start_index] > '0' and str[start_index] <= '9':
				one_check = self.checkString(str, start_index + 1, cache)
			sub_string = str[start_index:start_index + 2]
			if start_index + 2 <= len(str):
				if sub_string >= '10' and sub_string <= '26':
					two_check = self.checkString(str, start_index + 2, cache)
		cache[start_index] = int((one_check + two_check) % self.modulo)
		return cache[start_index]

	def CountWays(self, str):
		cache = [-1] * len(str)
		return self.checkString(str, 0, cache)


class Solution:

	def CountWays(self, str):
		n = len(str)
		if n == 0:
			return 1
		if str[0] == '0':
			return 0
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			oneDigit = int(str[i - 1])
			twoDigit = int(str[i - 2:i])
			if oneDigit >= 1:
				dp[i] += dp[i - 1]
			if twoDigit >= 10 and twoDigit <= 26:
				dp[i] += dp[i - 2]
		return dp[n] % (10 ** 9 + 7)


class Solution:

	def CountWays(self, str):
		ans = [0 for i in range(len(str) + 1)]
		ans[0] = 1
		ans[1] = 1
		for i in range(2, len(str) + 1):
			if str[i - 1] > '0':
				ans[i] = ans[i - 1]
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] >= '0' and (str[i - 1] <= '6')):
				ans[i] += ans[i - 2]
		return ans[len(str)] % (10 ** 9 + 7)


mod = 1000000000.0 + 7

class Solution:

	def CountWays(self, digits):
		n = len(digits)
		count = [0] * (n + 1)
		count[0] = 1
		count[1] = 1
		for i in range(2, n + 1):
			count[i] = 0
			if digits[i - 1] > '0':
				count[i] = count[i - 1]
			if digits[i - 2] == '1' or (digits[i - 2] == '2' and digits[i - 1] < '7'):
				count[i] = int((count[i] + count[i - 2]) % mod)
		return count[n]


class Solution:

	def CountWays(self, digits):
		n = len(digits)
		count = [0] * (n + 1)
		count[0] = 1
		count[1] = 1
		for i in range(2, n + 1):
			if digits[i - 1] > '0':
				count[i] = count[i - 1]
			if digits[i - 2] == '1' or (digits[i - 2] == '2' and digits[i - 1] < '7'):
				count[i] += count[i - 2]
			count[i] = count[i] % 1000000007
		return count[n]


class Solution:

	def CountWays(self, str):
		if str[0] == '0':
			return 0
		n = len(str)
		mod = 1000000007
		dp = [0 for i in range(n + 1)]
		dp[0] = dp[1] = 1
		for i in range(1, n):
			if str[i] == '0' and str[i - 1] > '2':
				return 0
		for i in range(2, n + 1):
			if str[i - 1] > '0':
				dp[i] = dp[i - 1]
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] < '7'):
				dp[i] += dp[i - 2]
			dp[i] %= mod
		return dp[n]


class Solution:

	def CountWays(self, str):
		mod = 1000000007
		if str[0] == '0':
			return 0
		dp0 = 1
		dp1 = 1
		for i in range(2, len(str) + 1):
			curr = 0
			if str[i - 1] != '0':
				curr += dp1
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] <= '6'):
				curr += dp0
			(dp0, dp1) = (dp1, curr)
		return dp1 % mod


class Solution:

	def CountWays(self, str):
		mod = 1000000007
		if str[0] == '0':
			return 0
		prev0 = 1
		prev1 = 1
		for i in range(2, len(str) + 1):
			curr = 0
			if str[i - 1] != '0':
				curr += prev1
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] <= '6'):
				curr += prev0
			(prev0, prev1) = (prev1, curr)
		return prev1 % mod


class Solution:

	def decode(self, digits, n, count, dp):
		if n == 0 or n == 1:
			return 1
		if digits[0] == 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		if digits[n - 1] > '0':
			count = self.decode(digits, n - 1, count, dp)
		if digits[n - 2] == '1' or (digits[n - 2] == '2' and digits[n - 1] < '7'):
			count += self.decode(digits, n - 2, count, dp)
		dp[n] = count
		return count

	def CountWays(self, digits):
		count = 0
		dp = [-1] * (len(digits) + 1)
		dp[0] = dp[1] = 1
		count = self.decode(digits, len(str), count, dp)
		return count % (10 ** 9 + 7)


class Solution:

	def CountWays(self, str):
		if len(str) == 1:
			return 1
		dp = [0] * len(str)
		if str[0] == '0':
			return 0
		dp[0] = 1
		if str[1] != '0':
			dp[1] = 1
		if str[0:2] <= '26':
			dp[1] += 1
		mod = 10 ** 9 + 7
		for i in range(2, len(str)):
			if str[i] == '0':
				if str[i - 1] == '0':
					return 0
				if str[i - 1] == '1' or str[i - 1] == '2':
					dp[i] += dp[i - 2] % mod
			elif str[i - 1] == '0':
				dp[i] += dp[i - 1] % mod
			else:
				dp[i] += dp[i - 1] % mod
				if str[i - 1:i + 1] <= '26':
					dp[i] += dp[i - 2] % mod
		return dp[len(str) - 1] % mod


class Solution:

	def CountWays(self, s):
		d = [0] * len(s)
		if s[0] != '0':
			d[0] = 1
		else:
			return 0
		for i in range(1, len(s)):
			if s[i] != '0':
				d[i] += d[i - 1]
			g = s[i - 1] + s[i]
			h = int(g)
			if s[i - 1] != '0' and h <= 26 and (h > 0):
				if i - 2 >= 0:
					d[i] += d[i - 2]
				else:
					d[i] += 1
		return d[-1] % 1000000007


class Solution:

	def CountWays(self, str):
		memo = {}

		def dfs(s):
			if s in memo:
				return memo[s]
			if not s:
				return 1
			if int(s[0]) == 0:
				return 0
			l = dfs(s[1:])
			r = 0
			if len(s) >= 2 and int(s[:2]) < 27:
				r = dfs(s[2:])
			memo[s] = l + r
			return l + r
		mod = 1000000007
		return dfs(str) % mod


class Solution:

	def func(self, str, n, dp):
		m = 1000000007
		if n == 0 or n == 1:
			return 1
		if dp[n] != -1:
			return dp[n]
		cnt = 0
		if str[n - 1] >= '1':
			cnt = cnt + self.func(str, n - 1, dp) % m
		if str[n - 2] == '1' or (str[n - 2] == '2' and str[n - 1] <= '6'):
			cnt = (cnt + self.func(str, n - 2, dp) % m) % m
		dp[n] = cnt % m
		return dp[n]

	def CountWays(self, str):
		n = len(str)
		if str[0] == '0':
			return -1
		dp = [-1] * (n + 1)
		return self.func(str, n, dp)


import math

class Solution:

	def CountWays(self, str):
		mod = 1000000007
		dp = [0 for i in range(len(str) + 2)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, len(str) + 1):
			if str[i - 1] != '0':
				dp[i] = dp[i - 1]
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] <= '6'):
				dp[i] = (dp[i] + dp[i - 2]) % mod
		return dp[len(str)]


class Solution:

	def CountWays(self, s):
		if s[0] == '0':
			return 0
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			if s[i - 1] != '0':
				dp[i] += dp[i - 1]
			if s[i - 2:i] >= '10' and s[i - 2:i] <= '26':
				dp[i] += dp[i - 2]
			dp[i] %= 1000000007
		return dp[n]


class Solution:

	def CountWays(self, str):
		MOD = 10 ** 9 + 7
		n = len(str)
		dp = {n: 1}

		def f(i):
			if i in dp:
				return dp[i]
			if str[i] == '0':
				return 0
			ans = f(i + 1)
			if i + 1 < n and (str[i] == '1' and str[i + 1] in '0123456789' or (str[i] == '2' and str[i + 1] in '0123456')):
				ans += f(i + 2)
			dp[i] = ans
			return ans % MOD
		return f(0) % MOD


class Solution:

	def CountWays(self, str):
		if str[0] == '0':
			return 0
		dp = [0] * (len(str) + 1)
		dp[0] = dp[1] = 1
		mod = 10 ** 9 + 7
		for i in range(2, len(str) + 1):
			one = int(str[i - 1])
			two = int(str[i - 2:i])
			if 10 <= two <= 26:
				dp[i] += dp[i - 2]
			if 1 <= one <= 9:
				dp[i] += dp[i - 1]
			dp[i] %= mod
		return dp[-1] % mod


class Solution:

	def CountWays(self, str):
		mod = 1000000007
		dp = []

		def rec(i, str, dp):
			if i == len(str):
				return 1
			if dp[i] != -1:
				return dp[i]
			c1 = 0
			c2 = 0
			if str[i] >= '1' and str[i] <= '9':
				c1 = rec(i + 1, str, dp)
			part = str[i:i + 2]
			if i <= len(str) - 2 and part >= '10' and (part <= '26'):
				c2 = rec(i + 2, str, dp)
			dp[i] = (c1 + c2) % mod
			return dp[i]
		dp = [-1] * len(str)
		return rec(0, str, dp)


class Solution:

	def CountWays(self, str):
		md = 10 ** 9 + 7
		n = len(str)
		tem = [0] * (n + 1)
		tem[0] = 1
		for i in range(n):
			if str[i] != '0':
				tem[i + 1] = tem[i + 1] + tem[i]
			if str[i - 1] != '0' and i - 1 >= 0 and (int(str[i - 1:i + 1]) <= 26):
				tem[i + 1] = (tem[i + 1] + tem[i - 1]) % md
		return tem[n]


class Solution:

	def CountWays(self, str):
		if not str:
			return 0
		dp = [0 for i in range(len(str) + 1)]
		dp[0] = 1
		if str[0] == '0':
			dp[1] = 0
		else:
			dp[1] = 1
		for i in range(2, len(str) + 1):
			if 0 < int(str[i - 1:i]) <= 9:
				dp[i] = dp[i] + dp[i - 1]
			if 10 <= int(str[i - 2:i]) <= 26:
				dp[i] = dp[i] + dp[i - 2]
		return dp[len(str)] % (10 ** 9 + 7)


class Solution:

	def CountWays(self, s):

		def isValid(n):
			if n == '' or n[0] == '0':
				return False
			n = int(n)
			if n == 0 or n > 26:
				return False
			return True
		n = len(s)

		def f(i):
			if i == n:
				return 1
			if dp[i] != -1:
				return dp[i]
			count = 0
			if i + 1 <= n and isValid(s[i:i + 1]):
				count += f(i + 1)
			if i + 2 <= n and isValid(s[i:i + 2]):
				count += f(i + 2)
			dp[i] = count
			return dp[i]
		dp = [-1] * n
		return f(0) % 1000000007


class Solution:

	def CountWays(self, str):
		if str[0] == 0 or str.__contains__('00'):
			return 0
		str_len = len(str)
		if str_len == 0 or str_len == 1:
			return 1
		dp = [-1] * (str_len + 1)
		return self.validate_message(str, str_len, dp) % 1000000007

	def validate_message(self, str, location, dp):
		if location == 0 or location == 1:
			return 1
		if dp[location] != -1:
			return dp[location]
		valid_message_count = 0
		char_check = int(str[location - 1])
		prev_char_check = int(str[location - 2])
		if char_check != 0:
			valid_message_count += self.validate_message(str, location - 1, dp)
		if prev_char_check == 1 or (prev_char_check == 2 and char_check <= 6):
			valid_message_count += self.validate_message(str, location - 2, dp)
		dp[location] = valid_message_count
		return dp[location]


class Solution:

	def CountWays(self, str):
		if len(str) == 0:
			return 1
		memory = {}
		return self.helper(0, str, memory) % (10 ** 9 + 7)

	def helper(self, i, str, memory):
		if str[i:] in memory:
			return memory[str[i:]]
		if i >= len(str):
			return 1
		elif str[i] == '0':
			return 0
		elif i == len(str) - 1:
			return 1
		elif str[i] == '1' or (str[i] == '2' and (int(str[i + 1]) >= 0 and int(str[i + 1]) <= 6)):
			count = self.helper(i + 1, str, memory) + self.helper(i + 2, str, memory)
			memory[str[i:]] = count
			return count
		else:
			count = self.helper(i + 1, str, memory)
			memory[str[i:]] = count
			return count


class Solution:

	def CountWays(self, str):
		s = str
		hm = {}
		for i in range(1, 27):
			hm['{}'.format(i)] = 1
		dp = [0 for i in range(len(s) + 1)]
		dp[0] = 1
		for i in range(len(s)):
			if s[i] in hm:
				dp[i + 1] = dp[i]
			if i > 0 and s[i - 1] + s[i] in hm:
				dp[i + 1] += +dp[i - 1]
		return dp[-1] % 1000000007


class Solution:

	def CountWays(self, str):
		n = len(str)
		count = [0] * (n + 1)
		count[0] = 1
		count[1] = 1
		for i in range(2, n + 1):
			count[i] = 0
			if str[i - 1] > '0':
				count[i] = count[i - 1]
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] < '7'):
				count[i] += count[i - 2]
		return count[n] % (10 ** 9 + 7)


class Solution:

	def CountWays(self, strx):
		n = len(strx)
		if n == 0:
			return 1
		if strx.find('00') >= 0 or strx[0] == '0':
			return 0
		for i in range(3, 10):
			if strx.find(i.__str__() + '0') >= 0:
				return 0
		strx = strx.replace('10', 'A')
		strx = strx.replace('20', 'A')
		n = len(strx)
		dp = [-1 for i in range(n + 1)]

		def mask(i):
			if dp[i] != -1:
				return dp[i]
			if i == n:
				return 1
			c = 0
			if i < n - 1 and strx[i + 1] == '0':
				c = mask(i + 2)
			else:
				c = mask(i + 1)
				if i < n - 1 and (strx[i] == '1' and ord(strx[i + 1]) < ord('A') or (strx[i] == '2' and ord(strx[i + 1]) <= ord('6'))):
					c = (c + mask(i + 2)) % 1000000007
			dp[i] = c
			return c
		return mask(0)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:
	mod = 10 ** 9 + 7
	arr = []

	def fun(self, ind, st, n):
		if ind == n:
			return 1
		if self.arr[ind] != -1:
			return self.arr[ind]
		take = 0
		leave = 0
		if st[ind] >= '1' and st[ind] <= '9':
			leave = self.fun(ind + 1, st, n)
		if ind < n - 1:
			tmp = st[ind:ind + 2]
			if '10' <= tmp <= '26':
				take = self.fun(ind + 2, st, n)
		t = (take + leave) % self.mod
		self.arr[ind] = t
		return t

	def CountWays(self, str):
		self.arr = [-1] * len(str)
		return self.fun(0, str, len(str))


class Solution:

	def CountWays(self, str):
		m = 1000000007
		if str[-1] == '0':
			first = 0
			second = 1
		else:
			first = 1
			second = 1
		for i in range(len(str) - 1)[::-1]:
			if str[i] == '0':
				if first == 0:
					return 0
				else:
					second = first
					first = 0
			elif str[i] == '1' or (str[i] == '2' and int(str[i + 1]) <= 6):
				sum = first + second
				second = first
				first = sum
			elif first == 0:
				return 0
			else:
				second = first
		if first == 0:
			return 0
		else:
			return first % m


class Solution:

	def CountWays(self, string):

		def dfs(i):
			if i >= len(string):
				return 1
			if string[i] == '0':
				return 0
			if i in mem:
				return mem[i]
			c = 0
			c += dfs(i + 1)
			if string[i] == '1' and i + 1 < len(string):
				c += dfs(i + 2)
			if string[i] == '2' and i + 1 < len(string) and (int(string[i + 1]) <= 6):
				c += dfs(i + 2)
			mem[i] = c
			return c % MOD
		MOD = 10 ** 9 + 7
		mem = {}
		return dfs(0)


class Solution:

	def CountWays(self, str):

		def fun(i):
			if i == n:
				return 1
			if i > n:
				return 0
			if dp[i] != -1:
				return dp[i]
			ans = 0
			if str[i] != '0':
				ans += fun(i + 1)
			if str[i] != '0' and int(str[i:i + 2]) < 27:
				ans += fun(i + 2)
			ans = ans % 1000000007
			dp[i] = ans
			return dp[i]
		n = len(str)
		dp = []
		for i in range(n):
			dp.append(-1)
		return fun(0)


class Solution:

	def CountWays(self, str):
		mod = 10 ** 9 + 7
		n = len(str)
		prev1 = 1
		prev2 = 1
		for i in range(2, n + 1):
			curr = 0
			if str[i - 1] != '0':
				curr = prev1
			if str[i - 2] == '1' or (str[i - 2] == '2' and str[i - 1] <= '6'):
				curr = (curr + prev2) % mod
			prev2 = prev1
			prev1 = curr
		return prev1