Để kích hoạt được cổng thời gian, bạn cần truyền vào đó hai mảnh vỡ năng lượng có tần số cộng hưởng triệt tiêu lẫn nhau tạo ra đúng một mức năng lượng K. Bạn đang có một túi chứa N mảnh vỡ năng lượng. Hãy kiểm tra xem có bao nhiêu cách ghép hai mảnh vỡ khác nhau trong túi để tạo ra mức năng lượng K đó? (Hai cách ghép được coi là khác nhau nếu vị trí của ít nhất một mảnh vỡ trong túi là khác nhau).

Input:

Dòng 1: Hai số nguyên N, K (1 <= N <= 10^5, |K| <= 10^9).

Dòng 2: N số nguyên A1, ..., AN là mức năng lượng của mỗi mảnh vỡ (|A_i| <= 10^9).

Output: Số lượng cặp thỏa mãn.

Ví dụ:

Input:

5 6
1 5 2 4 3

Output:

2

Trong một cuốn sách phép thuật cổ xưa, câu thần chú mạnh nhất luôn được giấu ở từ dài nhất của đoạn văn bản. Các từ trong đoạn văn được tách biệt bởi khoảng trắng hoặc các ký hiệu đặc biệt như dấu phẩy, dấu chấm, hỏi chấm, chấm than. Hãy tạo một công cụ tự động quét đoạn văn và tìm ra câu thần chú đó. Nếu có nhiều từ cùng đạt độ dài cực đại, câu thần chú chính là từ đầu tiên mà mắt bạn nhìn thấy từ trái sang.

Input: Một dòng chứa xâu S (Độ dài <= 10^5).

Output: Từ dài nhất tìm được (chỉ chứa chữ cái).

Ví dụ:

Input:

Hoc sinh gioi, mon Tin hoc!

Output:

sinh

Một trang trại có N tấm pin năng lượng mặt trời xếp thành một hàng ngang. Ban quản lý cần cung cấp gấp một mức điện năng ít nhất là S cho nhà máy. Để thuận tiện cho việc đấu nối dây cáp, họ phải chọn một dãy các tấm pin đứng liên tiếp nhau. Tuy nhiên, việc bảo trì rất tốn kém nên họ muốn số lượng tấm pin phải bật đó là ít nhất có thể. Hãy xác định xem họ cần bật ít nhất bao nhiêu tấm pin?

Input:

Dòng 1: Hai số nguyên N, S (1 <= N <= 10^5, 1 <= S <= 10^14).

Dòng 2: N số nguyên dương Ai là công suất của từng tấm pin (1 <= Ai <= 10^9).

Output: Số lượng tấm pin ít nhất cần bật. Nếu tổng toàn bộ trang trại không đủ S, in 0.

Ví dụ:

Input:

6 15
5 1 3 5 10 7

Output:

2

Bạn đang tham gia một show truyền hình thực tế và thử thách là phải vượt qua một dòng suối rộng bằng cách nhảy qua N tảng đá. Bạn có thể nhảy một bước sang tảng đá tiếp theo, hoặc nhảy xa qua 2 tảng đá. Đội ngũ sản xuất đã âm thầm bôi mỡ trơn trượt lên M tảng đá, nếu chạm vào đó bạn sẽ rơi xuống nước. Từ vị trí xuất phát (trước tảng đá thứ 1), bạn có bao nhiêu kịch bản di chuyển an toàn để đến được bờ bên kia (bước lên tảng đá thứ N)? Kết quả có thể rất lớn nên hãy chia lấy dư cho 10^9+7.

Input:

Dòng 1: Hai số nguyên N, M (1 <= N <= 10^5, 0 <= M <= N).

Dòng 2: M số nguyên phân biệt là vị trí các tảng đá bị trơn trượt.

Output: Số cách di chuyển modulo 10^9+7.

Ví dụ:

Input:

6 1
3

Output:

4