KIỂM TRA TRỰC TUYẾN HOÀNG VĂN THỤ - HÒA BÌNH

Giải mã văn tự MayA là một nhiệm vụ phức tạp hơn so với các nghiên cứu trước đây. Trên thực tế, sau gần 200 năm người ta chưa làm sáng tỏ gì nhiều lắm trong lĩnh vực này. Chỉ trong phạm vi ba thập niên cuối này mới có những tiến bộ đáng kể trong nghiên cứu.

Văn tự May A đặt cơ sở dựa vào các hình vẽ nhỏ, được biết dưới dạng các nét vạch biểu diễn âm tiết. Từ trong tiếng May A thường được viết dưới dạng  ô vuông chứa một một số các nét vạch. Đôi khi một từ bị bổ dọc thành nhiều ô hoặc một ô lại chứa nhiều nét vạch  hơn số nét cần thiết cho một từ.

Một trong số các vấn đề liên quan tới giải mã văn tự May A nảy sinh khi xác định trình tự đọc âm tiết. Khi điền các vạch vào ô vuông, đôi khi người May A lại quy trình trình tự đọc dựa trên các tiêu chuẩn thẩm mỹ riêng chứ không theo một quy luật chung. Điều này dẫn đến việc, ngay cả khi đã biết rõ âm tiết của nhiều nét vạch, các nhà khảo cổ học cũng không dám khẳng định chắc chắn cách phát âm cả từ.

Các nhà khảo cổ đang khảo sát một từ W cụ thể. Họ biết những nét gạch tạo thành từ đó, nhưng không biết hết các cách vẽ chúng. Các nhà khảo cổ sẽ chọ bạn biết g nét gạch tạo thành từ W và dãy S các nét vạch (theo trình tự xuất hiện) của câu đang khảo sát. Hãy xác định các khả năng xuất hiện từ W trong câu được khảo sát.

NHIỆM VỤ

Cho các nét vạch tạo thành từ W và dãy S các nét vạch trong bản văn tự chạm trổ. Hãy lập trình xác định số khả năng xuất hiện từ W trong S. Vì mọi trình tự xuất hiện các nét vạch trong W đều là chấp nhận được, các nhà khảo cổ yêu cầu bạn tìm số lượng dãy các nét vạch liên tiếp trong S, mỗi dãy tương ứng với hoán vị g nét vạch trong W.

Input

• Dòng 1: Chứa 2 số nguyên g và |S| viết rời nhau. (1 ≤ g ≤ 3000, g ≤ |S| ≤ 3.10⁶)
• Dòng 2: Chứa g nét vạch liên tiếp nhau tạo thành W.
• Dòng 3: Chứa |S| ký tự liên tiếp biểu diễn S.
• Input chỉ chứa các ký tự in hoa, in thường

Output

• Chứa số khả năng xuất hiện W trong S

Example

Input:
4 11
cAda
AbrAcadAbRa

Output:
2

* Giải thích ví dụ: Hai lần xuất hiện tại vị trí thứ 3 và thứ 4 (Xâu S được bắt đầu tính từ vị trí thứ 0)