Bài tập

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Hãy xác định xem có bao nhiêu số nguyên \(x\) trong đoạn \([l, r]\) mà \(x\) không chia hết cho bất kỳ số \(a_i\) nào.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, l, r\) (\(1 \le n \le 18\), \(1 \le l \le r \le 10^{18}\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là đáp án của bài toán.

Example

3 10 20
3 4 5

5

Scoring

• Subtask 1 (30% số điểm): \(1 \le l \le r \le 10^6\).
• Subtask 2 (70% số điểm): \(1 \le l \le r \le 10^{18}\).

Cho số nguyên dương \(N\) và hai số nguyên tố \(A, B\).
Hỏi có bao nhiêu số không lớn hơn \(N\) chỉ chia hết cho \(A\) hoặc \(B\)?

Input

Vào từ tệp văn bản CHIAHET.INP gồm:

• Dòng 1 ghi số nguyên dương \(N\);
• Dòng 2 ghi 2 số nguyên tố \(A, B\).

Output

Ghi ra tệp văn bản CHIAHET.OUT một số là kết quả của bài toán.

Example

10
2 3

6

Scoring

• Subtask 1: Có 36 test (90%) tương ứng 5,4 điểm với \(N \le 10^6\), \(A, B < N\);
• Subtask 2: Có 4 test (10%) tương ứng 0,6 điểm với \(10^6 < N \le 10^9\), \(A, B < N\).

Trong giờ hình học, An được thầy giáo dạy về công thức tính diện tích của hình chữ nhật và hình vuông. An thấy hình vuông rất đẹp nên cậu định nghĩa một hình chữ nhật "đẹp" là hình chữ nhật có các đặc điểm sau:

• Độ dài hai cạnh là các số nguyên dương.
• Diện tích bằng diện tích của một hình vuông có độ dài cạnh là một số nguyên dương.

An đã phát biểu định nghĩa này trước lớp và thách đố bài toán như sau:

Cho số nguyên dương \(x\). Tìm số nguyên dương \(y\) nhỏ nhất để \(x\) và \(y\) là độ dài hai cạnh của một hình chữ nhật "đẹp".

Yêu cầu
Giúp cả lớp tìm số nguyên dương \(y\) thỏa mãn bài toán của An.

Input

Nhập từ tệp văn bản B1.INP, gồm một dòng duy nhất chứa số nguyên dương \(x\).

Output

Ghi ra tệp văn bản B1.OUT, gồm một dòng duy nhất chứa số nguyên dương \(y\).

Example

4

1

6

6

8

2

Scoring

• \(90\%\) số test thỏa mãn \(1 \le x \le 10^6\).
• \(10\%\) số test thỏa mãn \(10^6 < x \le 10^{12}\).

Bạn được cho một bảng số gồm \(n\) hàng và \(m\) cột. Trong mỗi ô của bảng, bạn được điền một con số từ \(1\) đến \(k\). Tuy nhiên có ràng buộc đặc biệt là trong mỗi hàng và mỗi cột của bảng thì phải chứa ít nhất \(1\) ô được điền số \(1\).

Nhiệm vụ của bạn là đếm số cách điền bảng trên sao cho thỏa mãn ràng buộc.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 1000, 1 \leq k \leq 10^9)\), lần lượt là số hàng, số cột và số con số có thể sử dụng để điền vào bảng.

Output

In ra số cách điền bảng trên. Vì kết quả có thể rất lớn, in ra đáp án khi chia dư cho \(10^9 + 7\).

Example

2 2 3

17

3 4 3

101089

Scoring

• Có \(20\%\) số điểm ứng với \(n \times m \le 20\).
• Có \(30\%\) số điểm ứng với \(n, m \le 500\).
• Có \(50\%\) số điểm ứng với \(n, m \le 1000\).