Digits Decoding Problem

Ninja has a string of characters from 'A' to 'Z', encoded using their numeric values (A=1, B=2, ..., Z=26). The encoded string is given as a sequence of digits (SEQ). The task is to determine the number of possible ways to decode this sequence back into a string consisting only of characters from 'A' to 'Z'.

Input:

The first line of input contains an integer T denoting the number of 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:
1
121

Output:
3

Explanation:

The sequence 121 can be decoded as:
1. 1 = A, 2 = B, 1 = A so ABA
2. 12 = L, 1 = A so LA
3. 1 = A, 21 = U so AU
Thus, there are 3 ways: [ABA, LA, AU].

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10⁵
• 0 <= SEQ[i] <= 9
• Time limit: 1 sec

Note:

The input sequence will always have at least 1 possible way to decode.
The answer should be returned modulo 10^9 + 7.
Space optimization is encouraged for solving.