Công ty XD chuyên sản suất gạch xây tường, khi các viên gạch ra lò chờ xuất bán, các viên gạch được sắp thành hình tháp. Có ~N~ hàng gạch, hàng trên cùng có ~A~ viên gạch. Biết hàng dưới nhiều hơn hàng kề trên ~B~ viên. Hỏi để xếp được ~N~ hàng gạch đó người ta đã dùng bao nhiêu viên gạch?

Dữ liệu:

• Một dòng chứa 3 số nguyên ~N~, ~A~, ~B~.

Kết quả:

• Số nguyên duy nhất – số lượng viên gạch đã dùng.

Ví dụ

Input

5 1 1

Output

15

Giới hạn:

• ~N ≤ 2.10^{12} ; A ≤ 20; B ≤ 20~.

Cho số tự nhiên ~n~. Hãy viết chương trình tính ~S = 1^3 + 2^3 + 3^3 + … + n^3~.

Dữ liệu vào:

• Gồm một dòng duy nhất chứa số nguyên ~n~ (~1 \le n \le 10^9~).

Dữ liệu ra:

• Ghi một giá trị duy nhất làị số dư của phép chia ~S~ cho ~10^9+7~

Ví dụ:

Input1

3

Output1

36

Input2

4

Output2

100

Ràng buộc:

• 70% test ứng với giới hạn ~1 \le n \le 10^4~
• 30% test ứng với các trường hợp còn lại

Viết chương trình cho phép phân tích một số ra thừa số nguyên tố và ghi kết quả dưới dạng tích các lũy thừa.

Ví dụ: ~300 = 2^2.3.5^2~

Dữ liệu vào:

• Gồm 1 dòng duy nhất chứa số nguyên dương ~N~ (~2 \le n \le 10^7~)

Dữ liệu ra:

• Gồm 1 dòng duy nhất kết quả bài toán (In ra theo định dạng như ví dụ dưới)

Input1

12

Output1

2^2.3

Input2

13

Output2

13

Với một số nguyên dương n thì luôn tồn tại một cách phân tích n thành tích của các thừa số nguyên tố. Ví dụ: số 28 sẽ phân tích thành tích 2×2×7.

Yêu cầu: Cho số nguyên dương n, hãy phân tích n thành tích của các thừa số nguyên tố.

Input:

• Dòng đầu tiên: Ghi số nguyên dương n ~(2 ≤ n ≤ 2×10^9)~.

Output:

• Dòng đầu tiên: Ghi dãy số nguyên dương là các thừa số nguyên tố của n, các số được ghi theo thứ tự không giảm và cách nhau ít nhất một dấu cách.

Example:

Input:

28

Output:

2 2 7

Cho ~P~ là tập hợp các ước số dương không nguyên tố của số nguyên dương ~n~. Hãy tìm số phần tử của tập hợp ~P~.

Dữ liệu vào

• Một dòng duy nhất là giá trị của ~n~ (~1 ≤ n ≤ 10^{14}~)

Dữ liệu ra

• Một dòng duy nhất là số phần tử của ~P~

Ví dụ:

Input

20

Output

4

Input2

180

Output2

15

Cho số tự nhiên ~N~ (~N ≤ 10^7~). Hãy lập trình tìm tất cả bộ ba số nguyên tố ~x, y, z~ thỏa mãn:

• 𝑥~ < 𝑦 < 𝑧 ≤𝑁~

• ~𝑥^2 + 𝑦^2 =𝑧~

Dữ liệu vào:

• Một số nguyên dương ~N~ duy nhất.

Dữ liệu ra:

• Gồm nhiều dòng, mỗi dòng chứa một bộ ba số nguyên tố tìm được. Trong trường hợp không tìm được bộ ba số nguyên tố thỏa mãn đề bài thì đưa ra -1.

Ví dụ:

Input1

30

Output1

2 3 13
2 5 29

Input2

12

Output2

-1

Input3

300

Output3

2 3 13
2 5 29
2 7 53
2 13 173
2 17 293

Cho một số nguyên dương N.

Yêu cầu: Tìm T là số cách phân tích số N thành tổng của các số nguyên dương liên tiếp.

Ví dụ: N= 15. Có 3 cách phân tích số 15 thành tổng các số nguyên dương liên tiếp như sau: 15 = 1+2+3+4+5 = 4+5+6 = 7+8

Input:

• Nhập vào một số nguyên dương N ~(2 < N ≤ 10^8)~

Output:

• Ghi ra số T tìm được

Example:

Input:

15

Output:

3

Hôm nay Hùng dạy em trai học toán, làm quen với các con số. Hùng thấy em mình khá thông minh, việc so sánh các số bình thường có vẻ quá đơn giản đối với em trai. Vì vậy, Hùng ra yêu cầu mới, các số bình thường sẽ được đọc từ trái sang phải, bây giờ sẽ đọc ngược lại từ phải sang trái.

Yêu cầu: Cho hai số nguyên dương a và b, em hãy cùng em trai của Hùng đưa ra số có giá trị lớn hơn khi đọc 2 số này theo yêu cầu mới (~1 ≤ a, b ≤ 10^{18}~).

Input

• Gồm một dòng chứa hai số nguyên dương ~a~ và ~b~ khác nhau, cách nhau một dấu cách.

Output

• In ra số có giá trị lớn hơn (theo yêu cầu mới của Hùng).

Scoring

• Có 50% số điểm ứng với các test có ~1 ≤ a, b ≤ 10^9~.
• Có 50% số điểm ứng với các test có ~10^{10} ≤ a, b ≤ 10^{18}~.

Examples

Input

456 368

OutputCopy

863

Input

130 92

Output

31

Note

• Ở ví dụ 1, số 456 viết ngược là 654, số 368 viết ngược là: 863.

• Ở ví dụ 2, số 130 viết ngược là 31 (số 0 ở đầu được loại bỏ), số 92 viết ngược là 29.

Cho bốn số nguyên dương ~A, B, C, D~.

Yêu cầu: Hãy đếm xem có bao nhiêu số nguyên dương X thỏa mãn tất cả các điều kiện sau:

• ~A ≤ X ≤ B~

• ~X~ không chia hết cho ~C~;

• ~X~ không chia hết cho ~D~;

Dữ liệu vào:

• Một dòng duy nhất ghi 4 số nguyên dương ~A, B, C, D~ (với ~1 ≤ A ≤ B ≤ 10^{18}; 1 ≤ C, D ≤ 10^9~)

Dữ liệu ra:

• Một dòng duy nhất ghi số lượng số nguyên dương ~X~ thỏa mãn điều kiện của đề bài.

Ví dụ

Input:

4 9 2 3

Output

2

Giải thích:

• Chỉ có số 5 và 7 thỏa mãn điều kiện đề bài.