Bài tập

Trong làng Omega có một ông phú hộ rất giàu có. Tài sản của ông rất nhiều trâu, bò, và cả... ruộng vườn. Một hôm ông gọi 3 người con đã đến tuổi trưởng thành đến, và định chia cho mỗi người một phần ruộng để làm ăn.

Ông có tổng cộng \(n\) thửa ruộng, mỗi thửa có diện tích nguyên dương. Ông muốn chia đều toàn bộ \(n\) thửa ruộng này cho 3 người con, sao cho:

• Mỗi người nhận một nhóm thửa ruộng (có thể không bằng nhau về số lượng).
• Tổng diện tích của ruộng mỗi người nhận phải bằng nhau.

Hỏi có bao nhiêu cách chia \(n\) thửa ruộng đó thành 3 phần sao cho thỏa điều kiện trên?

Chú ý: Hai cách chia được coi là khác nhau nếu có ít nhất một thửa ruộng được phân cho người khác.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \le n \le 20)\) --- số thửa ruộng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((100 \le a_i \le 5000)\) --- diện tích của từng thửa ruộng.

Output

In ra một số nguyên là số cách chia hợp lệ. Nếu không thể chia được, in ra -1.

Example

5
100 200 250 50 30

-1

Cho một số tự nhiên \(N\). Hãy thay đổi tối đa hai chữ số của \(N\) để được một số nhỏ nhất chia hết
cho \(4\). Số mới tạo thành phải có số chữ số bằng số chữ số của \(N\) và không chứa chữ số 0 ở đầu.

Input

Nhập vào một số tự nhiên \(N\) \((10 ≤ N ≤ 10^{15})\).

Output

Ghi ra một số là kết quả của bài toán.

Example

168

100

26622

16612

Scoring

• Nếu chương trình chạy đúng những trường hợp \(10 ≤ N ≤ 10^4\), thí sinh sẽ được \(40\) điểm;

• Nếu chương trình chạy đúng những trường hợp \(10 ≤ N ≤ 10^{15}\), , thí sinh sẽ được \(100\) điểm.

Cho số nguyên dương \(N\).

Yêu cầu: Hãy phân tích \(N\) thành thừa số nguyên tố và đếm ước số của \(N\).

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(N\).

Output

• Dòng thứ nhất ghi phân tích thừa số của \(N\).

• Dòng thứ hai ghi số lượng ước số của \(N\).

Example

10

2*5
4

Một số nguyên dương \(N\) được gọi là số hoàn hảo khi \(N\) bằng tổng các ước nguyên dương khác nó. Ví dụ: \(6\) có các ước nguyên dương khác nó là: \(1, 2, 3\) và \(1 + 2 + 3 = 6\) hay \(6\) là một số hoàn hảo, \(5\) không phải là số hoàn hảo.

Yêu cầu: Cho số nguyên dương \(N\) , hãy kiểm tra \(N\) có phải là một số hoàn hảo hay không?

Input

Nhập từ bàn phím số nguyên dương \(N\) \((1 ≤ N ≤ 1000000)\).

Output

Ghi ra màn hình một trong hai thông báo: "So hoan hao." hoặc "Khong phai la so hoan
hao.".

Example

6

So hoan hao.

5

Khong phai la so hoan hao.