Cho chiều dài và chiều rộng của một hình chữ nhật. Hãy tính chu vi và diện tích của hình đó.

Công thức: ~Chu vi = (dai + rong) \times 2~; ~Dien tich = dai \times rong~.

Input: Hai số nguyên dương d, r lần lượt là chiều dài và chiều rộng (~1 \le d, r \le 1000~).

Output: Dòng đầu in chu vi, dòng thứ hai in diện tích.

Ví dụ minh họa

Input:

4 3

Output:

14
12

Bạn đang chơi một trò chơi xây dựng. Bạn cần xây một tòa tháp có độ cao chính xác là H tầng. Trong cửa hàng vật phẩm, có hai loại khối gạch:

• Khối gạch nhỏ: Có độ cao 1 tầng, giá x vàng.
• Khối gạch lớn: Có độ cao 2 tầng, giá y vàng.

Với ba số nguyên dương H, x , y, hãy tính số vàng ít nhất cần chi trả để xây được tòa tháp cao đúng H tầng.

Input

• Dòng đầu tiên: Một số nguyên dương H là chiều cao cần xây ~( 1 \leq H \leq 10^9 )~.
• Dòng thứ hai: Hai số nguyên dương x và y ~( 1 \leq x, y \leq 10^9 )~.

Output

In ra một số nguyên duy nhất là chi phí tối thiểu.

Example

Test 1 Input

6
2 3

Output

9

Giải thích: Mua 3 khối gạch lớn (mỗi khối cao 2 tầng, giá 3 vàng). Tổng chiều cao = 6. Chi phí = 3 * 3 = 9. Nếu mua 6 khối nhỏ thì tốn 12 vàng.

Test 2 Input

5
2 5

Output

10

Giải thích: Mua 5 khối nhỏ (10 vàng) rẻ hơn việc mua 1 khối lớn 3 khối nhỏ (11 vàng) hoặc 2 khối lớn 1 khối nhỏ (12 vàng).

Viết chương trình nhập vào n số nguyên. In ra tổng của các số chia hết cho cả 2 và 3.

Dữ liệu vào Specification

• Dòng đầu tiên ghi số nguyên không âm n ( ~0 < n \le 10^6~ ).

• Dòng 2 ghi n số nguyên dương 32 bit cách nhau một dấu cách trống.

Dữ liệu ra Specification

• Đưa ra tổng của các số chia hết cho cả 2 và 3.

Sample Input

5
4 6 8 10 12

Sample Output

18

Sau chuỗi trận đầu mùa Premier League 2025-2026 bết bát khiến người hâm mộ phải "chui vào hang", thầy Quyết - một fan cứng của Manchester United - đã mất ngủ 7 ngày 7 đêm để tìm nguyên nhân.

Bằng kiến thức Thần số học uyên thâm, thầy nhận ra vấn đề không nằm ở huấn luyện viên, mà nằm ở "phong thủy" tuyến giữa. Thầy khẳng định: "MU đá kém là do thiếu sự kết hợp hoàn hảo giữa một số 6 (tiền vệ phòng ngự mỏ neo) và một số 8 (tiền vệ con thoi box-to-box)".

Theo lý thuyết của thầy, một đội hình "bất bại" phải được vận hành dựa trên các "Mã Gen Chiến Thắng". Một Mã Gen Chiến Thắng hợp lệ là một chuỗi ký tự chỉ bao gồm hai chữ số 6 và 8.

• Số 6 đại diện cho những pha tắc bóng dũng mãnh.
• Số 8 đại diện cho những đường chuyền kiến tạo đẳng cấp.
• Ví dụ: Mã 686 nghĩa là: Tắc bóng -> Chọc khe -> Tắc bóng.

Thầy Quyết muốn gửi bản kế hoạch này sang Anh. Tuy nhiên, tờ giấy A4 gửi đi chỉ đủ chỗ viết các Mã Gen có độ dài không quá ~N~ ký tự.

Yêu cầu: Thầy Quyết muốn liệt kê tất cả các Mã Gen Chiến Thắng có thể tạo ra (độ dài từ 1 đến ~N~) để HLV Amorim tha hồ lựa chọn. Hãy đếm xem có bao nhiêu mã như vậy?

Vì danh sách các vấn đề của MU dài như sớ Táo Quân, nên số lượng Mã Gen này cũng sẽ rất lớn. Hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào (Input)

• Một dòng duy nhất chứa số nguyên dương ~N~ (~1 \le N \le 10^{18}~) – Độ dài tối đa của Mã Gen mà thầy Quyết cho phép.

Dữ liệu ra (Output)

• Một số nguyên duy nhất là số lượng Mã Gen tìm được (lấy dư theo ~10^9 + 7~).

Ví dụ minh họa

Ví dụ 1:

Ví dụ 2: