配点 : 125点

問題文

この問題はEの制約強化版です。
NN 桁の 66 の倍数の各桁の和」の総和を求めてください。
ただし、答えが非常に大きくなる可能性があるので 109+710^9+7 で割ったあまりを出力してください。
TT 個のテストケースが与えられるので、それぞれに答えてください。

制約

  • 1T1041≦T≦10^4
  • 1N10121≦N≦10^{12}
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

TT
case1case_1
case2case_2
\vdots
case3case_3

各テストケースは以下の形式で与えられる。

NN

出力

TT 行出力してください。ii 行目には、 caseicase_i に対する答えを出力してください。


入出力例1

  • 入力
2
2
3
  • 出力
135
2025

入出力例2

  • 入力
3
100
200
300
  • 出力
304457820
252156756
348725208

109+710^9+7 で割ったあまりを出力することに注意してください。

提出


Go (1.21)