Số siêu nguyên tố là một số nguyên tố mà khi bỏ đi lần lượt từng chữ số ở phía bên phải, các số còn lại vẫn luôn là số nguyên tố. (Ví dụ 2333 là số siêu nguyên tố vì 2333, 233, 23, 2 đều là nguyên tố). Hãy tìm và in ra tất cả các số siêu nguyên tố có đúng N chữ số, theo thứ tự tăng dần.

Input: Số nguyên dương N (1 <= N <= 8).

Output: In ra các số thỏa mãn, mỗi số trên 1 dòng. Nếu không có số nào, không in gì cả.

Ví dụ:

Input:

2

Output:

23
29
31
37
53
59
71
73
79

Trong thuật giả kim, để biến khối kim loại mã số N thành vàng, bạn cần luyện nó cùng với một lượng hóa chất mã số X nhỏ nhất sao cho tích N * X là một số chính phương (số có căn bậc hai là một số nguyên). Hãy tìm số nguyên dương X đó.

Input: Số nguyên dương N (1 <= N <= 10^9).

Output: Số nguyên dương X nhỏ nhất.

Ví dụ:

Input:

12

Output:

3

(Giải thích: 12 * 3 = 36 là số chính phương. 3 là số nhỏ nhất).

Phân xưởng sản xuất có N thanh nhựa với độ dài khác nhau. Robot lắp ráp cần chọn ra đúng 3 thanh nhựa để ghép thành một khung hình tam giác. Theo bất đẳng thức tam giác, 3 thanh độ dài a, b, c ghép được khi và chỉ khi tổng độ dài 2 thanh bất kỳ luôn lớn hơn thanh còn lại. Hãy đếm xem có bao nhiêu cách chọn 3 thanh nhựa thỏa mãn.

Input:

Dòng 1: N (3 <= N <= 5000).

Dòng 2: N số nguyên độ dài Li (1 <= Li <= 10^9).

Output: Số lượng cách chọn tạo thành tam giác.

Ví dụ:

Input:

4
2 2 3 4

Output:

3

(Giải thích: Các bộ (2,2,3), (2,3,4) (hai lần do có 2 thanh dài 2)).

Mã vạch sản phẩm của trung tâm là một chuỗi nhị phân độ dài N (chỉ gồm 0 và 1). Để máy quét hoạt động không bị lỗi, chuỗi mã vạch này tuyệt đối không được chứa K bit 0 đứng liên tiếp nhau. Hãy tính số lượng mã vạch hợp lệ có thể được tạo ra. In phần dư cho 10^9+7.

Input: Hai số nguyên N, K (1 <= N, K <= 10^5).

Output: Số lượng mã vạch hợp lệ modulo 10^9+7.

Ví dụ:

Input:

4 2

Output:

8

(Giải thích: Các mã hợp lệ là: 1111, 1110, 1101, 1011, 1010, 0111, 0110, 0101. Các mã như 0011, 1001... bị loại vì có 2 số 0 kề nhau).

Cho dãy A và số K.

Hãy tính tổng của tất cả các "Tổng cửa sổ".

Tức là: Tính S1 = tổng(1..K), S2 = tổng(2..K+1), ...

Kết quả là S1 + S2 + ... + S(n-k+1).

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Output:

• Một số nguyên duy nhất.

Ví dụ 1:

Input:

4 2
1 2 3 4

Output:

15

Ví dụ 2:

Input:

3 1
5 5 5

Output:

15