Four Steps#13107

Four Steps

2.5 seconds
256 megabytes

You are given a string of length consisting of the characters 0, 1, 2, 3 and ?. Every character ? must be replaced by one of the digits , , , (different occurrences may be replaced by different digits).

For a string u_1 u_2 \ldots u_n of digits, a climb is a quadruple of indices i < j < k < l such that u_i = 0, u_j = 1, u_k = 2 and u_l = 3. The indices do not have to be adjacent.

Count the replacements for which the number of climbs in the resulting string is divisible by . Two replacements are different if some character ? is replaced by different digits in them. Since the answer can be large, print it modulo .

Input

The first line contains a single integer (1 \le t \le 10^5) — the number of test cases.

Each of the next lines contains a non-empty string consisting of the characters 0, 1, 2, 3 and ?.

The total length of all strings does not exceed 5 \cdot 10^5.

Output

For each test case print one integer — the number of replacements for which the number of climbs is divisible by , modulo .

Examples

Example 1

Loading
Loading

Note

In the first test case contains no characters ? and exactly one climb. The number is not divisible by , so the answer is .

In the second test case contains one character ?. If it is replaced by , or , the resulting string has no climbs, and is divisible by . If it is replaced by , the resulting string is 0123, which has one climb. So the answer is .

In the third test case every climb uses one of two occurrences of each digit, so there are 2 \cdot 2 \cdot 2 \cdot 2 = 16 climbs, and is divisible by . There are no characters ?, so the answer is .

In the fourth test case consists of four characters ?, so there are 4^4 = 256 replacements. Only the string 0123 has a climb (exactly one), and all the others have none, so the answer is .

In the fifth test case contains no climbs.