Thi thử 13

Dọc theo một con đường trên phố đi bộ, người ta trồng một hàng cây gồm \(n\) cây xanh có khoảng cách đều nhau. Để cho người đi bộ có thời gian ngồi nghỉ ngơi, ngắm phố, người ta đặt dưới hàng cây một số ghế đá theo quy tắc xen kẽ, cứ 2 cây liền kề nhau thì có một cây được đặt ghế đá, một cây để trống. Biết rằng để đặt một ghế đá dưới một gốc cây thì cần chi phí với số tiền là \(x\) đồng.

Hãy tính tổng chi phí để đặt được nhiều ghế đá nhất cho hàng cây.

Input

• Gồm một dòng ghi hai số nguyên \(n\) và \(x\) (\(1 \leq n \leq 10^9, 1 \leq x \leq 10^3\)), cách nhau một dấu cách.

Output

• Gồm một số nguyên duy nhất là kết quả tìm được của bài toán.

Example

7 50

200

Nam là người yêu thích các số nguyên tố chính vì vậy cậu ta thường tìm ra những số nguyên tố có tính chất đặc biệt để tạo mật khẩu cho các tài khoản facebook, zalo, mail… của mình. Nam đã phát hiện ra có những số nguyên tố mà tổng các chữ số của nó cũng là số nguyên tố. Xét các ví dụ:

• Số \(17\) có tổng các chữ số là \(8\) không phải là số nguyên tố, số như vậy Nam không thể chọn làm mật khẩu.
• Số \(32\) có tổng hai chữ số là \(5\) là số nguyên tố nhưng số như vậy Nam không thể chọn làm mật khẩu vì số \(32\) không phải là số nguyên tố.
• Số \(67\) có tổng hai chữ số của nó bằng \(13\) cũng là một số nguyên tố, Nam chọn những số nguyên tố như vậy làm mật khẩu cho tài khoản.

Cho hai số nguyên \(l, r\), hãy cho biết trong đoạn từ \(l\) đến \(r\) có những số nguyên tố nào Nam có thể chọn để làm mật khẩu cho tài khoản của mình?

Input

• Gồm hai số nguyên dương \(l, r\) (\(1 \leq l \leq r \leq 10^7\)) trên một dòng và cách nhau một dấu cách. Dữ liệu luôn đảm bảo có bài toán có nghiệm.

Output

• Gồm các số nguyên tố đặc biệt từ \(l\) đến \(r\). Các số trên một dòng được in ra theo thứ tự và cách nhau một dấu cách.

Example

50 90

61 67 83 89

Cho công thức hóa học của phân tử một chất dưới dạng xâu kí tự. Các nguyên tử trong công thức chỉ bao gồm H (Hydro), O (Oxy), N (Nitrogen) và C (Carbon). Trong đó:

• H có nguyên tử lượng là 1
• O có nguyên tử lượng là 16
• N có nguyên tử lượng là 14
• C có nguyên tử lượng là 12

Trong công thức, nếu có một nguyên tử \(E\) nào đó gặp liên tiếp \(n\) lần thì sẽ được viết gọn thành \(En\) (\(n \leq 1000\)). Phân tử lượng là tổng khối lượng các nguyên tử trong phân tử.

Giả sử công thức hóa học N203 có phân tử lượng là \(14 \times 2 + 16 \times 3 = 76\)

Cho công thức hóa học. Hãy xác định phân tử lượng của công thức hóa học đã cho.

Input

• Gồm một dòng chứa chuỗi kí tự \(S\) (\(|S| \leq 10^5\)) xác định công thức hóa học của phân tử

Output

• Gồm một dòng duy nhất chứa phân tử lượng dưới dạng số nguyên.

Example

N2O3

76

Flashback là một loại virus máy tính sinh sản rất nhanh khi có môi trường thuận lợi và là một loại virus nguy hiểm, có tốc độ lây lan nhanh trong môi trường mạng.

Flashback lần đầu tiên được phát hiện vào năm 2011 bởi công ty diệt virus Intego dưới dạng một bản cài đặt Flash giả và chúng sinh sản theo quy tắc sau:

• Ngày đầu tiên (ngày \(0\)) có \(n\) có cá thể ở mức \(1\).
• Ở mỗi ngày tiếp theo, mỗi cá thể mức \(i\) sinh ra \(i\) cá thể mức \(1\), các cá thể mới sinh sẽ sinh sôi, phát triển từ ngày hôm sau.
• Bản thân các cá thể mức \(i\) phát triển thành mức \(i + 1\) và chu kì phát triển trong ngày chấm dứt.

Hãy xác định sau \(k\) ngày trong môi trường mạng có bao nhiêu cá thể.

Input

• Gồm một dòng chứa hai số nguyên \(n, k\) (\(1 \leq n \leq 1000, 1 \leq k \leq 10^5\)).

Output

• Gồm một số nguyên - số lượng cá thể virus theo mô đun \(10^9 + 7\).

Scoring

• Có 40% số test ứng với 40% số điểm có \(N \leq 100, k \leq 10^3\)
• Có 60% số test ứng với 40% số điểm có \(N \leq 1000, k \leq 10^5\)

Example

5 3     

65