A message containing letters from 'A' to 'Z' is being encoded into numbers using the following encoding:

'A' -> 1
'B' -> 2
.
.
.
'Y' -> 25
'Z' -> 26

Given an encoded string, find the number of ways it can be decoded.

Examples

decoded: 123
encoded: ["ABC", "LC", "AW"]
answer: 3

decoded: 36
encoded: ["CF"]
answer: 1

decoded: 106
encoded: ["JF"]
answer: 1

decoded: 306
encoded: []
answer: 0

The total number of ways to decode can be larger than the largest 32 bit number. Return your answer with module 10⁹ + 7.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has a string denoting the decoded string

Output Format

For each test case, the output contains a line with one integer denoting the total number of ways. Return the answer with module 10⁹ + 7.

Sample Input

4
123
36
106
306

Expected Output

3
1
1
0

Constraints

1 <= T <= 30
1 <= length of string <= 104
The string contains only digits and may contain leading zeroes