Một tài liệu sau khi mã hóa thành một xâu kí tự S có độ dài m bao gồm các chữ cái tiếng Anh sẽ được gửi đi kèm theo với mật mã là một xâu kí tự T có độ dài n cũng gồm các chữ cái tiếng Anh. Do đường truyền không ổn định nên khi gửi tài liệu, có thể một số kí tự của xâu S bị thay bằng kí tự *. Quá trình giải mã, người ta xét tất cả các xâu con liên tiếp độ dài n của S, gọi là: P0, P1, ..Pm-n.

Yêu cầu: Tính số các xâu Pi (i=0..m-n) có thể là hoán vị của xâu T, nếu trong xâu Pi có chứa các kí tự * thì được phép thay mỗi kí tự * đó thành chữ cái tiếng Anh bất kì.

Dữ liệu: Vào từ tệp văn bản CAU3.INP gồm:

• Dòng đầu chứa hai số nguyên dương n, m (n ≤ 3.10^3, m ≤ 3.10^6);
• Dòng thứ hai chứa xâu kí tự T;
• Dòng thứ ba chứa xâu kí tự S.

  Kết quả: Ghi ra tệp văn CAU3.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

CAU3.INP
    3 12
    aab
    abcnbaabfkjd
CAU3.OUT
    2
CAU3.INP
    3 4
    abc
    a**c
CAU3.OUT
    2

Ràng buộc:

• Có 40% số điểm có: độ dài xâu S không quá 1000 và xâu S không chứa kí tự *;
• Có 40% số điểm tiếp theo có: xâu S không chứa kí tự *;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.