Secret Message Decoding Problem

Ninja encountered an encoded secret message where each character from 'A' to 'Z' is mapped to a numeric value (A = 1, B = 2, ..., Z = 26). Given a numeric sequence (SEQ) derived from such encoding, determine how many ways the sequence can be decoded back into a valid string.

Input:

The first line contains an integer T representing the number of test cases.
Each test case consists of a single line with a digit sequence.

Output:

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

Example:

Input:

1
121

Output:

3

Explanation:

Three possible decodings for sequence '121' are 'ABA', 'LA', and 'AU'.

Constraints:

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

Note:

Input sequence will always have at least 1 valid decoding.
Return the answer modulo 10^9 + 7.
You are not required to print anything as this is handled by the framework. Implement the function logic.