老师又布置了一份困难的数学作业，你必须在截止日期前完成它。

这份作业与除法运算有关，旨在练习被小整数整除。你需要统计所有恰好由 $N$ 位数字组成的非负整数（允许前导零），且这些数字满足一定的整除要求。例如，假设你想统计由 2 位数字组成，且能被 6 整除但不能被 5 整除的数，满足这些要求的数字有：06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78 和 96。

注意，零可以被任何正整数整除（请查看第三个样例测试）。

因为 $N$ 可能非常大，所以你决定编写一个程序来帮你完成这份作业。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 1,000$)，表示测试用例的数量。接下来的 $T$ 行，每行代表一个测试用例，包含一个整数 $N$ ($1 \le N \le 10^{18}$)，表示你需要统计的数字的长度，随后是一个空格，紧接着是一个 6 位的字符串（每一位数字为 '0', '1' 或 '2'）。其中第 $i$ 位数字（最左侧的数字为第 1 位）如果为 '0'，则表示如果数字不能被 $i$ 整除，则该数符合要求；如果为 '1'，则表示如果数字能被 $i$ 整除，则该数符合要求；如果为 '2'，则表示无论数字能否被 $i$ 整除，该数均符合要求。

输出格式

对于每个测试用例，请在单独的一行中输出一个整数，即满足上述条件的数字的个数。由于结果可能非常大，请输出其对 $1,000,000,007$ ($10^9 + 7$) 取模后的结果。

样例

输入 1

4
2 222201
1 111001
1 111111
2 222222

输出 1

13
1
1
100