Cho một dãy số \(A\) có \(N\) phần tử. Tìm số nguyên dương \(P\) nhỏ nhất thỏa mãn: \(P\) là số chính phương và \(P\) chia hết cho tất cả các phần tử của dãy số \(A\).

Yêu cầu: In ra phần dư của phép chia khi chia \(P\) cho \(10^9+7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng phần tử của dãy số.
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là các phần tử của dãy số \(A\) (\(1 \le i \le N\)).

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 10, a_i \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^4, a_i \le 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5, a_i \le 10^7\).

Example

3
2 1 3

36

Mít mới học ba định nghĩa mới liên quan đến dãy số như sau:

• Một dãy số được gọi là dãy đầy đủ bậc \(K\) khi dãy só có đúng \(K\) phần tử và gồm đủ các phần tử từ \(1\) đến \(K\). Ví dụ dãy số \((2,3,1)\) là dãy số đầy đủ bậc \(3\).
• Dãy số \(B\) được gọi là dãy con của dãy số \(A\) khi dãy số \(B\) được tạo ra bằng cách xóa bộ một số phần tử của dãy số \(A\) (giữ nguyên thứ tự trước sau và có thể không xóa bỏ phần tử nào). Ví dụ dãy số \(A\) là \((4,2,1,2,5,6)\), một số dãy số con của dãy số \(A\) là \((4,1,6)\); \((2,2,5,6)\); \((4;2;1;2;5;6)\);...
• Dãy số \(A\) được gọi là có thứ tự từ điển nhỏ hơn dãy số \(B\) khi tồn tại vị trí \(i\) mà:
  • Với mọi vị trí \(j\) (\(j < i\)) thì \(a_j = b_j\).
  • \(a_i < b_i\).

Sau khi đã học xong lý thuyết, thầy giáo đã giao cho Mít một bài tập rất khó: cho một số \(K\) và dãy số \(A\) có \(N\) số nguyên dương không lớn hơn \(K\). Hãy tìm dãy con của dãy số \(A\) có thứ tự từ điển nhỏ nhất và là một dãy đầy đủ bậc \(K\).

Yêu cầu: Hãy lập trình giúp Mít tìm dãy con thỏa mãn yêu cầu của thầy giáo.

Input

• Dòng đầu tiên chứa một số nguyên dương \(T\) (\(T \le 5\)) là số bộ dữ liệu.
• Mỗi bộ dữ liệu có cấu trúc như sau:
  • Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) là số lượng phần tử của dãy số \(A\) và số \(K\) cho trước (\(2 \le K \le N\)).
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(x\) là các phần tử của dãy số \(A\) (\(x \le K\)).

Output

• Với mỗi bộ dữ liệu ghi ra một dãy con thỏa mãn yêu cầu. Dữ liệu đảm bảo luôn có kết quả.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 18\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 30\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 10^5, K \le 10\).
• Subtask \(4\) (\(30\%\) số điểm): \(K \le N \le 10^5\).

Example

2
4 3
3 2 1 2
8 4
4 2 3 3 1 3 2 4

3 1 2
1 3 2 4

Bản đồ mặt bẳng của một công trình xây dựng là một hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị (\(m,n \le 10^6\)), các hàng ô của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới và các cột ô của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên giao của hàng \(x\) và cột \(y\) được gọi là ô \((x,y)\).

Mùa mưa đến, người ta muốn tôn cao mặt bằng của công trình để tránh ngập úng bằng cách dùng \(k\) (\(k \le 10^6\)) chuyến xe ben chở đất đá bên ngoài đổ vào mặt bằng công trình. Chuyến xe thứ \(i\) đổ vào ô \((x_i,y_i)\) đúng \(a_i\) tấn đất đá (\(a_i\) là số nguyên, \(\forall i:1 \le i \le k\)). Tổng khối lượng đất đá được các chuyến xe ben đổ vào công trình là số nguyên không vượt quá \(10^{12}\) và chia hết cho \(m \times n\).

Tiếp theo, máy ủi được điều tới để san đều toàn bộ khối lượng đất đá này vào các ô. Chi phí để máy ủi chuyển mỗi tấn đất đá từ một ô sang một ô khác kề cạnh là \(1\) (chú ý là không được chuyển đất ra khỏi mặt bằng công trình).

Yêu cầu: Tìm cách điều khiển các máy ủi để san đều toàn bộ khối lượng đất đá vào các ô với chi phí ít nhất. Cho biết chi phí đó.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(m,n,k\).
• \(k\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(x_i,y_i,a_i\).

Output

• Một số nguyên duy nhất là chi phí san đều toàn bộ khối lượng đất đá vào các ô theo phương án tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m \le 2\).
• Subtask \(2\) (\(25\%\) số điểm): \(m,n \le 20\).
• Subtask \(3\) (\(25\%\) số điểm): \(m,n \le 2000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

3 3 4
1 1 4
1 1 5
3 1 3
3 2 6

18