Digits Decoding Problem Statement

A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes, he encoded each character of the string to its numeric value, that is, A = 1, B = 2, C = 3, till Z = 26, and combined them as a single sequence (SEQ) of digits of length N.

Today, he is trying to decode the numeric sequence into some valid string. A valid string is a string with characters from A to Z and no other characters. Decode the sequence and count the number of ways it can be decoded to a valid string.

Input:

The first line of input contains an integer T denoting the number of queries or test cases. 
The first and only line of each test case contains a digit sequence.

Output:

For each test case, print the number of ways to decode the given digit sequence in a separate line.

Example:

Input: 
SEQ = 121

Output:
3

Explanation:

The first way to decode 121 is: 1 = A, 2 = B, 1 = A which gives ABA.

The second way is: 12 = L, 1 = A giving LA.

The third way is: 1 = A, 21 = U resulting in AU.

Thus, there are 3 ways to decode the sequence 121: [(ABA), (LA), (AU)].

Constraints:

• 1 <= T <= 10
• 1 <= N <= 105
• 0 <= SEQ[i] <= 9

Time Limit: 1 sec

Note:

The input sequence will always have at least 1 possible way to decode. As the answer can be large, return your answer modulo 10^9 + 7.

Follow Up:

Can you solve this using constant extra space?