Xâu con tốt

Cho xâu $s$ gồm các chữ cái Latin thường. Mỗi chữ cái trong bảng chữ cái được đánh dấu là tốt hoặc xấu.

Xâu con $s[l\dots r]$ (với $1\le l\le r\le |s|$) là xâu $s_l{s}_{l+1}\dots s_r$. Xâu con này được gọi là tốt nếu trong các ký tự $s_l,s_{l+1},\dots ,s_r$ có không quá $k$ ký tự xấu.

Hãy đếm số xâu con tốt đôi một khác nhau của $s$. Hai xâu con được coi là khác nhau khi nội dung của chúng khác nhau, tức là hai xâu con giống hệt nhau nhưng nằm ở vị trí khác nhau chỉ được tính một lần.

Dữ liệu vào

• Dòng đầu tiên chứa xâu $s$ khác rỗng, gồm các chữ cái Latin thường.
• Dòng thứ hai chứa xâu gồm đúng $26$ ký tự "0" hoặc "1". Nếu ký tự thứ $i$ bằng "1" thì chữ cái thứ $i$ của bảng chữ cái là tốt, ngược lại là xấu. Ký tự đầu tiên ứng với chữ "a", ký tự thứ hai ứng với chữ "b", và cứ như vậy.
• Dòng thứ ba chứa số nguyên $k$ là số ký tự xấu tối đa được phép xuất hiện trong một xâu con tốt.

Dữ liệu ra

In ra một số nguyên duy nhất là số xâu con tốt đôi một khác nhau của $s$.

Ràng buộc

• $1\le |s|\le 1500$
• $0\le k\le |s|$

Ví dụ