Dino đang học về thời gian. Bố đố Dino: giả sử hiện tại là 00:00:00, hỏi sau ~N~ giây thì là thời gian nào? Bạn hãy cùng Dino giải quyết bài toán này.

Dữ liệu vào từ tệp văn bản: NGIAY.INP

• Gồm một dòng chứa một số nguyên ~N~ ~(0 \le N < 86400)~.

Kết quả ghi ra tệp văn bản: NGIAY.OUT

In ra trên một dòng chuỗi thời gian dưới định dạng HH:MM:SS, trong đó:

• HH: giờ ~(0 \le HH ≤ 23)~.
• MM: phút ~(0 \le MM \le 59)~.
• SS: giây ~(0 \le SS \le 59)~.

Sample Input 1

59

Sample Output 1

00:00:59

Sample Input 2

3661

Sample Output 2

01:01:01

Cho một xâu ~X~ có độ dài xâu không quá ~10^4~, chỉ gồm các kí tự tiếng Anh in hoa. Viết liên tiếp ~K~ lần xâu ~X~ được xâu ~S~. Hỏi có bao nhiêu xâu HN được tạo ra bằng cách xoá các kí tự từ xâu ~S~.

Dữ liệu vào từ tệp văn bản: DEMHN.INP

• Dòng đầu tiên chứa xâu ~X~;
• Dòng thứ hai chứa một số nguyên dương ~K~ (~K \leq 10^9~).

Kết quả ghi ra tệp văn bản: DEMHN.OUT

• In ra kết quả của bài toán sau khi chia lấy dư cho ~10^9 + 7~.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~K = 1~;
• Subtask 2 (~20\%~ số điểm): ~K \leq 10^3~;
• Subtask 3 (~20\%~ số điểm): ~K \leq 10^6~;
• Subtask 4 (~10\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

HNNH
2

Sample Output

8

Giải thích

• Xâu ~S~ có dạng HNNHHNNH.
• Các bộ vị trí tạo thành xâu HN thỏa mãn là ~(1, 2), (1, 3), (1, 6), (1, 7), (4, 6), (4, 7), (5, 6), (5, 7)~.

Bạn được cho hai số nguyên dương ~N~ và ~X~. Hãy đếm số lượng số tự nhiên có ~N~ chữ số mà chia hết cho ~2^X~.

Dữ liệu vào từ tệp văn bản: CHIAHET2.INP

Bạn sẽ phải trả lời bài toán trên ~T~ lần:

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T \le 10^3~).
• ~T~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~N, X~ ~(1 \le N \le 18, 0 \le X \le 60)~ là dữ liệu của câu hỏi thứ ~i~.

Kết quả ghi ra tệp văn bản: CHIAHET2.OUT

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bài toán thứ ~i~.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~T \le 10, N \le 6~.
• Subtask 2 (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2
2 4
3 3

Sample Output 1

6
112

Giải thích: Các số có ~2~ chữ số chia hết cho ~2^4~ là: ~16, 32, 48, 64, 80, 96~.

Sample Input 2

1
1 3

Sample Output 2

2

Hùng đang trải nghiệm tựa game mới mua đầu năm, trong màn chơi hiện tại thì Hùng đang gặp một trở ngại khá lớn. Màn chơi có ~N~ tòa tháp, tòa tháp thứ ~i~ có độ cao là ~H_i~. Hiện tại ở tòa tháp thứ ~1~, Hùng đang có một chiếc máy bay với độ an toàn bay là ~K~. Trong một lần bay, Hùng có thể điều khiển máy bay từ tòa tháp ~i~ bay đến một tòa tháp ~j~ ~(i < j)~, với điều kiện ~|H_i - H_j| \le K~ vì nếu không máy bay có thể đâm vào tháp và cậu sẽ thua.

Cho dữ liệu của màn chơi, bạn hãy kiểm tra xem với mỗi tòa tháp thì có tồn tại cách để Hùng bay đến hay không?

Dữ liệu vào từ tệp văn bản: CHOIGAME.INP

• Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(1 \le N \le 2 \cdot 10^5)~ và ~K~ ~(1 \le K \le 10^9)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~H_1, H_2, \ldots H_N~, với ~H_i~ là độ cao của tòa tháp thứ ~i~ ~(1 \le H_i \le 10^9)~.

Kết quả ghi ra tệp văn bản: CHOIGAME.OUT

• In ra trên một dòng ~N~ số nguyên ~0~ hoặc ~1~, số thứ ~i~ là ~1~ nếu Hùng có thể bay đến tòa tháp đó, và ~0~ nếu ngược lại.

Subtasks

• Subtask 1 (~40\%~ số điểm): ~H_1 < H_2 < \ldots < H_N~.
• Subtask 2 (~30\%~ số điểm): ~N \le 1000~.
• Subtask 3 (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

5 2
5 4 8 7 2

Sample Output

1 1 0 1 1

Giải thích: Hùng có thể đi đến các tòa tháp ~1, 2, 4, 5~ như sau:

• Tháp ~1~: Hùng ban đầu đã ở tháp ~1~.
• Tháp ~2~: Đi từ ~1~ đến ~2~.
• Tháp ~4~: Đi từ ~1~ đến ~4~.
• Tháp ~5~: Đi từ ~1~ đến ~2~ rồi đến ~5~.

Một dãy số ~x_1, x_2, \ldots, x_m~ được gọi là dominative nếu tồn tại một giá trị ~k~ xuất hiện nhiều hơn ~\frac{m}{2}~ lần. Ví dụ:

• Dãy ~[3, 2, 2]~ là dominative vì giá trị ~2~ xuất hiện ~2~ lần, lớn hơn ~\frac{3}{2}~.
• Dãy ~[1, 2, 3, 2]~ không phải dominative vì không có giá trị nào xuất hiện nhiều hơn ~\frac{4}{2} = 2~.

Yêu cầu

Cho dãy ~a_1, a_2, \ldots, a_n~, bạn cần đếm số cách chia dãy này thành các đoạn con liên tiếp sao cho mỗi đoạn con đều không dominative.

Dữ liệu vào từ tệp văn bản: DOMI.INP

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~).

Kết quả ghi ra tệp văn bản: DOMI.OUT

• In ra số cách chia thỏa mãn chia lấy dư cho ~10^9 + 7~.

Giới hạn

• Trong tất cả các test ~n \leq 2 \times 10^5~, ~a_i \leq 10^9~.
• ~18 \%~ số test có ~n \leq 100~.
• ~18 \%~ số test có ~n \leq 1000~.
• ~24 \%~ số test có ~n \leq 5000~.
• ~15 \%~ số test có ~1 \leq a_i \leq 2~.
• ~25 \%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4  
3 6 6 9  

Sample Output 1

2  

Sample Input 2

6  
1 2 1 2 1 2  

Sample Output 2

4  

Giải thích

• Ở test ví dụ đầu tiên, có 2 cách chia là ~[3, 6, 6, 9]~ hoặc ~[3, 6], [6, 9]~