Cho xâu \(S\) chỉ gồm chữ cái thường và số nguyên \(K\).

Tý muốn đếm số lượng xâu con khác nhau của \(S\) mà xuất hiện ít nhất \(K\) lần trong \(S\).

Hai xâu con được coi là khác nhau nếu độ dài hoặc thứ tự ký tự khác nhau.

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

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

Định dạng đầu ra

• Một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Input:

ababa
2

Output:

6

Giải thích: Các xâu con khác nhau: a, ab, aba, abab, ababa, b, ba, bab, baba. Trong đó xuất hiện ≥2 lần: a (3 lần), ab (2 lần), aba (2 lần), b (2 lần), ba (2 lần), bab (2 lần) → 6 xâu.

Ràng buộc