Hệ thống an ninh lượng tử sử dụng số tổ hợp chập K của N (ký hiệu là C(N, K)) để tạo khóa. Để bẻ khóa, bạn không cần tính chính xác giá trị khổng lồ của C(N, K), mà chỉ cần cho biết con số này có bao nhiêu chữ số 0 liên tiếp ở tận cùng.

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

Output: Số lượng chữ số 0 tận cùng của C(N, K).

Ví dụ:

Input:

10 4

Output:

1

(Giải thích: C(10, 4) = 210, có 1 chữ số 0 tận cùng).

Cấu trúc cân bằng vĩnh cửu yêu cầu 3 cột trụ có tổng sức chịu tải đúng bằng X. Bạn có N cột trụ với sức chịu tải A_i. Hãy đếm xem có bao nhiêu bộ 3 cột trụ (i, j, k) với 1 <= i < j < k <= N thỏa mãn tổng sức chịu tải của chúng đúng bằng X.

Input:

Dòng 1: N, X (3 <= N <= 3000, 1 <= X <= 10^9).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^8).

Output: Số lượng bộ 3 thỏa mãn.

Ví dụ:

Input:

6 10
1 4 2 5 3 6

Output:

3

(Giải thích: Các bộ là (1,4,5), (1,3,6), (2,5,3)).

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).

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).