Một bản tin số được mã hoá bậc thang như sau: với chuỗi chữ số $d_1d_2\ldots d_k$ (từ trái sang phải), giải mã bằng cách cộng các chữ số từ phải sang trái nhân với trọng số:

• chữ số phải cùng nhân $1!$,
• chữ số kế trái nhân $2!$,
• tiếp theo nhân $3!$, …
• nói chung, chữ số thứ $i$ từ phải sang nhân $i!$.

Yêu cầu

Cho $n$ bản tin (mỗi bản tin là một số). Hãy in giá trị giải mã cho từng bản tin theo quy tắc trên (in phần dư theo module $10^9+7$).

Dữ liệu

Vào từ thiết bị vào chuẩn:

• Dòng 1: số nguyên $n$ ($n \le 10^4$).
• $n$ dòng tiếp theo: mỗi dòng là một số thể hiện một bản tin.

Kết quả

Ghi ra thiết bị ra chuẩn $n$ dòng; dòng thứ $i$ là số dư trong phép chia có số bị chia là giá trị giải mã của bản tin thứ $i$ và số chia là $10^9+7$.

Ví dụ mẫu

4
135
402
7
9

17
26
7
9

Giới hạn

Subtask 1 (40% số điểm): Mỗi bản tin có không quá 6 chữ số;

Subtask 2 (40% số điểm): Mỗi bản tin có không quá 10 chữ số;

Subtask 3 (10% số điểm): Mỗi bản tin có không quá 18 chữ số;

Subtask 4 (10% số điểm): Tổng số chữ số của tất cả các bản tin không vượt quá $10^6$.