THTBTQ22 Số chính phương

Xem PDF



Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Python, Ruby, Rust, Scala, Swift
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\)\(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

Test 1

Input
5 2
8 4 6 18 5
Output
9
Note
  • Bội chung nhỏ nhất của dãy số A là 360.
  • Thay số \(4\) thành \(4 \times 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

Bình luận