" " "
Q: Này này tại sao học bài lại phải im lặng vậy chứ?
Q: Tớ ghét sự tĩnh lặng :<
C: Hmmmm
Q: Đây để tớ hát cho cậu nghe kkk :>
" " "

Một ngày nọ Q và C cùng nhau tìm hiểu về một tác phẩm văn học, ở nơi họ sinh sống văn học và chữ nghĩa vốn là một thứ xa xỉ mà ai cũng ao ước. Khát khao của hai người là học thật nhiều tri thức để có thể thay đổi thực tại của bản thân, trong trí nhớ của C thì tác phẩm cậu đọc được khi đó tồn tại một thanh âm ngân vang (có lẻ là tác phẩm trên) vì vậy cậu nôn nóng học thật nhanh để có thể đọc cho Q nghe. Sau khi học xong cậu nhanh chóng ghi ra giấy những gì mình đã học, thứ cậu ghi lên tờ giấy là một xâu S có độ dài là N để tiện cho việc xem lại. Nhưng thật chớ trêu thay cậu lại rất hay viết sai chính tả.....

Sau bao quá trình học tập C biết rằng mình thường viết sai chính tả một số chữ cái trong bảng chữ cái. Vì vậy cậu tự hỏi là mình đã ghi sai những gì trong chuỗi mình đã tự ghi ra. Nhưng vì ở gần Q một thời gian nên cậu cũng bị lây tính lười nên C quyết định giao việc này lại cho bạn.

C cung cấp cho bạn một mảng nhị phân ~a~ gồm ~26~ phần tử và một số ~K~, trong đó ~a_i~ với ~1 \le i \le 26~ chỉ mang hai giá là ~1~ hoặc ~0~ nghĩa là chữ cái thứ ~i~ trong bảng chữ cái mà C luôn ghi đúng và ngược lại.

Nhiệm vụ của bạn là hãy giúp C đếm xem có bao nhiêu xâu con riêng biệt mà số lượng chữ cái C ghi sai trong xâu con đó không được vượt quá ~K.~

Input:

• Dòng đầu tiên gồm một xâu ~S~ gồm các chữ cái tiếng anh viết thường có độ dài là ~N~ với ~1 \le N \le 2000.~

• Dòng thứ hai là mảng nhị phân ~a~ gồm ~26~ phần tử, trong đó ~a_i~ bằng ~1~ nghĩa là chữ cái thứ ~i~ trong bảng chữ cái mà C luôn viết đúng và ngược lại.

• Dòng thứ ba là số nguyên ~K~ với ~0 \le K \le N.~

Output

Đáp số của bài toán.

Sample Input 1

aaaaa
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1

Sample Output 1

5

Sample Input 2

tocacaumuoi
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0

Sample Output 2

61

Giải thích

Trong VD1, các xâu thỏa mãn sẽ là

• a
• aa
• aaa
• aaaa
• aaaaa

Bạn có thắc mắc vì sao xâu S lại chỉ gồm các ký tự tiếng anh viết thường không?

Vì tác phẩm trên là tiếng đàn ghita của lorca