Decoding Ways

You are given an encoded message containing digits. Each digit or pair of digits can be mapped to a letter using the mapping: \( 'A' = 1, 'B' = 2, \ldots, 'Z' = 26 \). Your task is to determine the number of ways to decode the message. Since the answer might be very large, output the result modulo \(10^9 + 7\).

For example, the message "12" can be decoded as "AB" (1 2) or "L" (12), so there are 2 ways in total.

Note: A decoded message must not contain leading zeros and every digit grouping must form a valid letter as per the given mapping.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a non-empty string consisting of digits representing the encoded message.

outputFormat

For each test case, output a single line containing the number of ways to decode the given message, computed modulo \(10^9 + 7\).

## sample

1
12

2

</p>