10. Tiếp tục đẩy độ khó lên một tí

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

Các số trên một dòng được ghi cách nhau bởi dấu cách

Output

= Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là kết quả của bài toán.

Example

3
2 1 3

36

Scoring

• Subtask \(1\): Có \(30\%\) số test ứng với \(N \le 10\), \(a_i \le 10\)
• Subtask \(2\): Có \(30\%\) số test khác ứng với \(N \le 10^4\), \(a_i \le 10^5\)
• Subtask \(3\): Có \(40\%\) số test còn lại ứng với \(N \le 10^5\), \(a_i \le 10^7\)

Một công xưởng đã sản xuất ra một dãy \(n\) con chip được gắn liền kề với nhau, con chip thứ \(i\) đang hoạt động ở công suất \(a_{i}\). Vì được gắn liền kề nhau nên công suất của những con chip có sự tác động lẫn nhau và làm ảnh hưởng đến công suất hoạt động của cả đoạn. Ta định nghĩa tổng công suất của các con chip trong một đoạn chip \([l, r]\) \((1 \leq l \leq r \leq n)\) được xác định bởi giá trị nhỏ nhất của đoạn chip đó. Để chiết xuất một đoạn chip hoạt động hiệu quả, nhà sản xuất muốn biết rằng với mỗi số nguyên \(x\) từ \(1\) đến \(n\), đoạn chip có độ dài \(x\) có tổng công suất lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^{5})\) là số lượng chip của công xưởng.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là công suất hoạt động của các con chip.

Output

• Gồm \(n\) số nguyên dương trên 1 dòng, số nguyên thứ \(x\) là tổng công suất lớn nhất của đoạn chip độ dài \(x\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(10\%\) số điểm): \(a_{i} \leq 100\).
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5000\).
• Subtask \(5\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

4
2 1 4 5

5 4 1 1

Vào ngày nghỉ, Đạt và Châu cùng nhau chơi tựa game Liên Minh Huyền Thoại. Để dạy Châu cách ra đòn đánh cuối cùng vào lính, Đạt đã tạo ra \(n\) con lính, con lính thứ \(i\) sẽ bị hạ gục khi nhận ít nhất \(a_{i}\) đòn đánh. Cả hai người đều sử dụng kĩ năng đánh thường, mỗi đòn đánh thường đều sẽ gây \(1\) sát thương cho lính. Hai người đánh các con lính lần lượt theo thứ tự từ \(1\) đến \(n\) cùng với nhau. Khi hạ gục con lính trước, hai người mới cùng chuyển sang đánh con lính sau. Nhân vật của Đạt có thể thực hiện \(x\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{x}\) giây, nhân vật của Đạt sẽ thực hiện một đòn đánh), còn nhân vật của Châu có thể thực hiện \(y\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{y}\) giây, nhân vật của Châu sẽ thực hiện một đòn đánh). Hỏi với mỗi con lính, người tiêu diệt con lính đó sẽ là ai, biết rằng người thực hiện đòn đánh cuối cùng sẽ được tính là người tiêu diệt con lính đó, nếu như hai người cùng thực hiện đòn đánh cuối cùng lên con lính cùng lúc thì sẽ tính là cả hai cùng tiêu diệt con lính đó.

Input

• Dòng thứ nhất chứa ba số nguyên \(n, x, y\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq x, y \leq 10^{6})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Với mỗi con lính bị tiêu diệt, in ra trên một dòng. Nếu con lính bị hạ gục bởi Đạt, in ra một dòng \texttt{D}, nếu con lính bị hạ gục bởi Châu, in ra một dòng \texttt{C}, nếu con lính bị hạ gục bởi cả hai người, in ra một dòng \texttt{Both}.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(x = 1, y = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(x = 1\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 1 2
5 6 10 12

Both
Both
C
Both

Hội thi Tin học trẻ được tổ chức hàng năm và đã thu hút được sự quan tâm của cả nước. Đề thi ngày càng phong phú và đa dạng là do sự đóng góp ý tưởng từ rất nhiều nhà khoa học và các tổ chức công nghệ. Đến nay, ngân hàng đề thi có tổng cộng \(n\) bài, các bài được đánh số từ \(1\) tới \(n\), bài thứ \(i\) có độ khó là \(i\). Để xây dựng đề thi năm nay, Ban giáo khảo muốn chọn \(k\) bài khác nhau từ ngân hàng đề thi mà tổng độ khó của \(k\) bài đúng bằng \(n\). Để khảo sát tính đa dạng của đề thi, Ban giám khảo muốn tính số cách xây dựng đề thi khác nhau (hai đề thi được gọi là khác nhau nếu có một bài được chọn trong đề thứ nhất nhưng không được chọn trong đề thứ hai).

Hãy giúp Ban giám khảo tính số cách xây dựng đề thi khác nhau. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n\) và \(k\).

Output

• Ghi ra một số nguyên duy nhất là số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Example

10 3

4

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\) và \(k \le 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6\) và \(k \le 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 2\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 3\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k \le 5\).