Phone System

Time Limit: 3 Seconds    Memory Limit: 32768 KB

Reading a large number on the phone for others, is one of challenging (!) tasks. We have an interactive voice response (IVR) phone service. To have a better recognition of your number, you are recommended to do the following instructions in order:  

  •  Read only single or two digit numbers
  •  You cannot read 0X as a two digit number
  •  Read minimum number of zeros (Sefr in Persian)
  •  And finally read minimum number of single-digit numbers

We want to know the number of possible ways that you can read the given number for our system following our recommendations?

Input

The first line of the input contains an integer T≤100 denoting the number of test-cases. Each test-case contains a number string consists of at most 200 digits.

Output

For each test-case, output on a single line the number of possible ways that you can read the numbers. Since the result may become very large, output the result modulo 1,000,000,007.

Sample Input

3
000
01020320
401234501234560

Sample Output

1
1
3
Submit

Source: 12th Iran Nationwide Internet Contest IV