Mặc dù học hành rất chăm chỉ nhưng Dani vẫn không nắm vững kiến thức toán học cơ bản. Hôm nay cô giáo cho bài tập tính các lũy thừa bậc \(b\) cơ số \(a\), Dani hiểu nhầm sang khái niệm bội số và tính hết thành \(a*b\).

Từ kết quả của Dani, bạn hãy lập trình giúp cô ấy tìm lại kết quả đúng, kết quả đúng luôn là giá trị lớn nhất có thể. Tuy nhiên nếu Dani "ăn may" ra kết quả đúng bạn hãy xuất ra dòng chữ "OK".

Do con số có thể rất lớn bạn hãy lấy số dư khi chia cho \(10^9 + 7\).

Đầu vào

Dòng đầu tiên chứa số tự nhiên \(t\) \((1 \le t \le 10^6)\), số lượng test con.

\(t\) dòng tiếp theo mỗi dòng chứa một số tự nhiên \(n\) là kết quả của Dani.

Tổng của \(n\) trong tất cả các testcase (đối với một bộ test) đảm bảo không vượt quá \(10^{12}\).

Đầu ra

\(t\) dòng, mỗi dòng chứa duy nhất một số tự nhiên hoặc xâu "OK".

Subtask

\(30\%\) số test có \(t = 1\).

Ví dụ

Đầu vào:

2
90
5

Đầu ra:

130653412
OK

Giải thích:

Trong testcase đầu tiên, \(90 = 2*45 = 3*30 = ...\), như vậy các giá trị có thể đúng là \(2^{45}, 3^{30}, ...\) Trong những số như vậy thì \(3^{30}\) đạt giá trị lớn nhất nên \(3^{30}\) là kết quả đúng; do đó ta xuất ra \(3^{30}\%(10^9 + 7) = 130653412\).

Trong testcase thứ hai, \(5^1 = 5*1\).