New update is available. Click here to update.

Digits Decoding

Posted: 10 Dec, 2020
Difficulty: Moderate


Try Problem

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. Let's say the message was "LA", Ninja encoded it as 121 for L=12 and A=1.

Today, when he read the encoded secret message, he realised that he was not able to decode the original string. So, the Ninja is wondering in how many ways he can decode the numeric sequence to some valid string.

A valid string is a string with characters from A to Z and no other characters.

Let the encoded sequence be 121,

The first way to decode 121 is:
1 = A
2 = B
1 = A
Thus, the decoded string will be ABA.

The second way to decode 121 is:
12 = L
1 = A
Thus, the decoded string will be LA.

The third way to decode 121 is:
1 = A
21 = U
Thus, the decoded string will be AU.

So, there will be 3 ways to decode the sequence 121 i.e. [(ABA), (LA), (AU)].
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?
Input format:
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 format:
For each test case, print the number of ways to decode the given digit sequence in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10   
1 <= N <= 10^5
0 <= SEQ[i] <= 9

Time limit: 1 sec