芸茹的课堂测试

题目描述

霍纳（Horner）规则是一种将一元n次多项式的求值问题转化为n个一次式的算法。采用最小的乘法运算策略，用于求多项式$A(x)=a_0+a_1x+a_2x^2+...+a_n-1x^n-1+a_nx^n$在x处的值，转化为$A(x)=a_0+x(a_1+x(a_2+...+x(a_n-1+xa_n)···))$。其伪代码如下：

y = 0
for i = n downto 0
    y = ai + x * y

给一个8进制数，这个数很大，他的长度甚至可以达到1e6（即10的6次方）。请输出这个数十进制意义下对1e9+7取模（即取余数）的结果。

输入

第一个数为数据组数n。n <= 10。

每组数据包括一行，一个大整数S，表示给定的8进制数x。S在字符串意义下长度不超过1e6。

输出

对于每组数据，输出一行，为其十进制下对1e9+7取模的值。

输入样例

2
22
2222222222222222222

输出样例

18
733442737