Cho xâu \(S\), đếm số xâu con phân biệt có độ dài chính xác bằng \(K\).

Định dạng đầu vào

• Dòng 1: xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng 2: số nguyên \(K\) (\(1 \le K \le |S|\)).

Định dạng đầu ra

• Một số nguyên là số xâu con phân biệt độ dài \(K\).

Ví dụ

Input:

ababa
3

Output:

2

Giải thích: Xâu con phân biệt độ dài 3: aba, bab.

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).