Cho văn bản dưới dạng một xâu ký tự 𝑇 = 𝑡1𝑡2 … 𝑡𝑛 (1 ≤ 𝑛 ≤ 10^6), một xâu con gồm 𝑘 ký tự liên tiếp của 𝑇 được gọi là một cửa sổ trượt (sliding window) độ dài 𝑘 của 𝑇 (1 ≤ 𝑘 ≤ 𝑛). Như vậy xâu 𝑇 có tất cả 𝑛 − 𝑘 + 1 cửa sổ trượt độ dài 𝑘.

Cho mẫu 𝑃 dưới dạng xâu ký tự 𝑃 = 𝑝1𝑝2 … , 𝑝𝑚 (1 ≤ 𝑚 ≤ 𝑛). Hãy cho biết có bao nhiêu cửa sổ trượt độ dài 𝑘 của 𝑇 mà trong mỗi cửa sổ trượt đó có sự xuất hiện của mẫu 𝑃.

Dữ liệu:

• Dòng 1: Chứa xâu 𝑇

• Dòng 2: Chứa mẫu 𝑃

• Dòng 3: Chứa số nguyên 𝑘

Kết quả:

Ghi số lượng các cửa sổ trượt tìm được

Sample Input

this is the first task 
is
4

Sample Output

6