Gauthami has to get dressed for a date. She is going to meet Prasanna in the poshest restaurant in the country of Thuvax.
Prasanna arrives early and sees the outfit she has picked.  
While waiting outside, Prasanna being a restless nerd calculates the number of ways she can get dressed.
 
The complete outfit she picks is represented as a string of digits. The digits represent the following details about the apparel:
(apparel = clothing or accessories or any other part of the outfit)
 
1 - a 2 piece apparel where first piece has to be worn before the other. It is followed by the description of the two pieces in order.
 
2 - a 2 piece apparel which can be worn in any order, and it is not necessary to complete one apparel before starting another one. It is followed by the description of the two pieces in order.
 
0 - a single piece of apparel which can be put on directly.
 
Help Prasanna calculate the number of ways in which Gautami can get dressed. Since Prasanna does not want to make Gauthami bored by telling her a huge number, he wants to tell her the number of ways modulo 1000000007.
 
For example, consider an outfit comprising of a shirt, a skirt into which the shirt has to be tucked in and  
a neck cloth worn over the shirt.
It will be represented as 10200 and the number of ways she can get dressed is 2(She has to wear the shirt first after which she can wear either the skirt after the neck cloth or neck cloth after the skirt).

Input

First line is a positive integer T (T<=100) representing the number of testcases 

It is followed by T lines, each containing a string S of digits (each digit will be one of 0,1,2) describing the outfit, 1<=|S|<=100,000

The complete outfit comprises of a single item.

Output

Output for each test case should consist of one line representing the number of ways in which Gauthami can get dressed modulo 1000000007.

Example

Input:
3 
10200 
0 
1102000

Output:
2 
1 
2