Cho dãy số nguyên dương gồm N phần tử a1, a2,...aN. Với phần tử ai của dãy số, số chính phương kết hợp của ai là số chính phương s lớn nhất thoa mãn: khi thay a, thành ai * s thì bội chung nhỏ nhất của dãy số A 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ử ai.

Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu tiên chứa hai số nguyên dương N và i (i ≤ N ≤ 10^6);

Dòng thứ hai gồm N số nguyên dương mô tả dãy số A, các số có giá trị không quá 10^7.

Kết quả: Ghi ra thiết bị ra chuẩn 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.

Ràng buộc:

Có 50% số test ứng với 50% số điểm của bài thỏa mãn: N ≤ 20; ai ≤ 20;

30% số test khác ứng với 30% số điểm của bài thoa mãn: N ≤ 10^3; ai ≤ 10^7;

20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Input:

5 2
8 4 6 18 5

Output:

9

Giải thích: Bội chung nhỏ nhất của dãy số A là 360. Thay số 4 thành 4 x 9 = 36 thì dãy số là 8,36,6,18,5 vẫn có bội chung nhỏ nhất là 360. Vậy kết quả là 9.