G - Rock (Hard)

配点 : 125点

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

• 入力はすべて整数

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

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

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

• 入力

2
2
3

• 出力

135
2025

• 入力

3
100
200
300

• 出力

304457820
252156756
348725208

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