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

Để tối ưu tốc độ, siêu máy tính không đọc biểu thức toán học theo cách thông thường mà dùng ký pháp hậu tố (Postfix). Trong ký pháp này, toán hạng đứng trước, toán tử đứng sau. Ví dụ: "3 4 +" nghĩa là 3 + 4. "3 4 2 * +" nghĩa là 3 + (4 * 2). Cho một biểu thức hậu tố hợp lệ chỉ gồm các số nguyên dương và 3 phép toán (+, -, *), hãy tính giá trị của biểu thức đó.

Input: Một dòng chứa biểu thức hậu tố, các số và phép toán cách nhau bởi khoảng trắng (Độ dài xâu <= 10^5, kết quả trung gian và cuối cùng đều vừa trong số nguyên 64-bit).

Output: Giá trị của biểu thức.

Ví dụ:

Input:

5 2 3 * + 4 -

Output:

7

(Giải thích: 5 + (2 * 3) - 4 = 7).

Một phi hành gia rơi vào lưới không gian N dòng M cột. Từ ô (i, j), phi hành gia chỉ có thể đi sang ô bên phải (i, j+1), đi xuống dưới (i+1, j), hoặc đi chéo xuống phải (i+1, j+1). Có K vùng dị thường trên lưới không thể bước vào. Bắt đầu từ ô (1, 1), hãy tính số cách để đi đến ô (N, M). In kết quả theo module 10^9+7.

Input:

Dòng 1: N, M, K (1 <= N, M <= 1000, 0 <= K <= N*M).

K dòng tiếp theo: Mỗi dòng chứa tọa độ r, c của vùng dị thường.

Output: Số cách đi modulo 10^9+7.

Ví dụ:

Input:

3 3 1
2 2

Output:

5

Một chuỗi S chứa các ký tự in thường đại diện cho các hàm trong một dự án phần mềm. Để dễ bảo trì, cần chia chuỗi S thành các đoạn (module) liên tiếp sao cho: Mỗi ký tự (hàm) chỉ xuất hiện hoàn toàn ở trong đúng một module. Em hãy tìm cách chia để thu được số lượng module là nhiều nhất.

Dữ liệu vào: Một chuỗi S duy nhất (độ dài 1 <= len(S) <= 1000).

Kết quả ra: Kích thước của từng module được chia, in cách nhau bởi dấu cách.

Ví dụ:

Input:

ababcbacadefegdehijhklij

Output:

9 7 8

(Đoạn 1: ababcbaca (9); Đoạn 2: defegde (7); Đoạn 3: hijhklij (8)).