Tích các số nguyên tố

Tạo một số $S$ độ dài vô hạn bằng cách ghép các số nguyên tố có giá trị tăng dần lại với nhau, bắt đầu từ số $2$. Các chữ số đầu tiên của $S$ là $23579111317192329...$

Cho $T$ testcase, mỗi testcase bao gồm một số nguyên dương $k$. Nhiệm vụ của bạn là tính tích $k$ chữ số đầu tiên của $S$. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi mod ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên dương $T$ thể hiện số testcase ($T\le {10}^5$).
• $T$ dòng sau, mỗi dòng gồm số nguyên dương $k$ ($k\le {10}^{18}$).

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng xuất ra kết quả ứng với testcase đó.

Ràng buộc

• $1\le T\le {10}^5$
• $1\le k\le {10}^{18}$
• 30% số điểm có $k\le 100100$.
• 70% số điểm còn lại không có giới hạn gì thêm.

Ví dụ