F. 超级回文数

对于一个非负整数，若将它倒序后仍然与原来相等，则称它为回文数。例如 $121$ 和 $2332$ 是回文数，而 $12$ 和 $324$ 则不是。

现在，vvvb 拿到了一个非负整数 $n$，他一眼就看出来 $n$ 是不是回文数了，这实在是没什么挑战性。因此 vvvb 决定加大难度。他将会从整数 $n$ 中任意截取一段构成一个新的非负整数 （该整数不能含有前导 $0$），若这个整数是回文数，那么 vvvb 的开心值就会增加这个整数的值。例如当 $n=12321$ 时，若 vvvb 截取了 $232$ 这一段，则他的开心值就会增加 $232$。现在 vvvb 对整数 $n$ 进行了所有可能的截取，他想知道他最后能获得的开心值是多少。显然这个开心值非常的大，因此你只需要最后将答案对 $10^9+7$ 取模即可。

注意，若一个回文数在 $n$ 中出现了多次，则它也需要被多次计算。

本题为多组样例，第一行一个正整数 $T(1\leq T\leq 10)$ 代表数据组数。

对于每组数据，输入一行一个非负整数 $n(0\leq n< 10^{100000})$，代表 vvvb 所拿到的数。

对于每组数据输出一行一个整数，代表 vvvb 最后能获得的开心值对 $10^9+7$ 取模后的答案。

样例输入

2
12321
10101

样例输出

12562
10306

样例解释

对于第一个样例 $12321$，可截取 $2$ 次 $1$，$2$ 次 $2$，$1$ 次 $3$，$1$ 次 $232$ 和 $1$ 次 $12321$，因此总和为 $2\times 1+2\times 2+1\times 3+1\times 232+1\times 12321=12562$；

对于第二个样例 $10101$，可截取 $3$ 次 $1$，$2$ 次 $0$，$2$ 次 $101$ 和 $1$ 次 $10101$，$010$ 由于含有前导 $0$ 不合法，因此总和为 $3\times 1+2\times 0+2\times 101+1\times 10101=10306$。