题目描述

对于所有正整数 $x$ ，函数 $f(x)$ 定义如下：

• 如果 $x$ 含有任何不是 $0$ 或 $1$ 的数字，那么对于 $x$ 的每一位：若该位是奇数则改成 $1$ ，否则改成 $0$ ，并返回得到的新数。
• 否则，返回 $x-1$ 。

给定一个 $x$ $(1 \leq x \leq 10^{2 \times 10^5})$ ，求需要对 $x$ 应用多少次 $f(x)$ 才能使 $x$ 变成 $0$ 。由于这个次数可能很大，输出它对 $10^9+7$ 取模的结果。

输入格式

第一行包含 $T$ $(1 \leq T \leq 10^5)$ ，表示独立测试用例个数。

接下来 $T$ 行，每行一个正整数 $x$ ，仅由数字 0-9 组成，且没有前导零。

保证所有输入整数的总位数不超过 $10^6$ 。

输出格式

对每个测试用例，输出所求次数对 $10^9+7$ 取模后的结果，每个结果占一行。

输入输出样例 #1

输入 #1

2
24680
210

输出 #1

1
4

输入输出样例 #2

输入 #2

1
1234567890123456789012345678901234567890

输出 #2

511620083

说明/提示

样例解释

第一个测试： $x$ 经过一次操作后变为零。

第二个测试： $f(x)=10,f^2(x)=9,f^3(x)=1,f^4(x)=0$

数据范围

• $1\leq T \leq 10^5$
• 每个测试中， $x$ 均为无前导零的正整数
• 每个 $x$ 的位数不超过 $2\times 10^5$ 位
• 所有测试用例中 $x$ 的总位数不超过 $10^6$