Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử \(a_1, a_2, \ldots, a_n\). Với phần tử \(a_i\) là số chính phương \(s\) lớn nhất thõa mãn: khi thay \(a_i\) thành \(a_i \times s\) thì bội chung nhỏ nhất của dãy số \(A\) là không đổi.

Yêu cầu: Cho dãy số \(A\) và vị trí \(i\), tìm số chính phương kết hợp của phần tử \(a_i\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(i\) (\(1 \le N \le 10^6\)).
• Dòng thứ hai gồm \(N\) số nguyên mô tả dãy số \(A\), các số có giá trị không quá \(10^7\).

Output

• Ghi ra thiết bị ra chuẩn bị một dòng gồm một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho \(10^9 + 7\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 20\), \(a_i \le 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^3\), \(a_i \le 10^7\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

5 2
8 4 6 18 5

9