G - Rock (Hard)

配点 : 125点

問題文

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

制約

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

入力

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

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

出力

$T$ 行出力してください。$i$ 行目には、 $case_i$ に対する答えを出力してください。

入出力例1

• 入力

2
2
3

• 出力

135
2025

入出力例2

• 入力

3
100
200
300

• 出力

304457820
252156756
348725208

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