题目描述

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$.

输入格式

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$.

输出格式

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

2
24680
210

1
4

1
1234567890123456789012345678901234567890

511620083

提示

Sample 1 Explanation

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$

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: Aiden Bai