Tích chính phương

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Pypy 3, Python, Scala
Điểm: 1200 (p) Thời gian: 0.15s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn được cho một tập hợp \(S\) gồm các số nguyên dương từ \(1\) đến \(n\). Nhiệm vụ của bạn là số chính phương lớn nhất là tích của một tập hợp con của \(S\).

Input, Output and Scoring

Input

  • Số nguyên dương \(n\).

Output

  • In ra kết quả sau khi chia lấy dư \(1234567891\).

Scoring

  • Subtask \(1\) \((20\%)\): \(1 \le n \le 20\).
  • Subtask \(2\) \((80\%)\): \(1 \le n \le 10^5\).

Input and Output

Input

6

Output

144
Note
  • Ta chọn tập hợp \({1, 2, 3, 4, 6}\) để có tích là số chính phương lớn nhất có thể.

Bình luận