For all positive integers $x$, the function $f(x)$ is defined as follows:

• If $x$ has any digits that aren't $0$ or $1$, for each digit of $x$, set it to $1$ if it is odd or $0$ otherwise, and return $x$.
• Otherwise, return $x-1$.

Given a value of $x$ ($1 \leq x < 10^{2\cdot 10^5}$), find how many times $f$ needs to be applied to $x$ until $x$ reaches $0$. As this number might be very large, output its remainder when divided by $10^9+7$.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$ ($1\le T\le 10^5$), the number of independent tests.

The next $T$ lines each contain a positive integer $x$ consisting solely of the digits 0-9, with no leading zeros.

It is guaranteed that the total number of digits in all input integers does not exceed $10^6$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the remainder of the number of times when divided by $10^9+7$ on a separate line.

SAMPLE INPUT:

2
24680
210

SAMPLE OUTPUT:

1
4

First test: $x$ becomes zero after one operation.

Second test: $f(x)=10, f^2(x)=9, f^3(x)=1, f^4(x)=0$

SAMPLE INPUT:

1
1234567890123456789012345678901234567890

SAMPLE OUTPUT:

511620083

SCORING:

• Inputs 3-5: $T\le 2000$, $x< 10^{9}$
• Inputs 6-7: $x < 10^{18}$
• Inputs 8-9: $x < 10^{60}$
• Inputs 10-12: No additional constraints.

Problem credits: Aidan Bai