You are given string $\boldsymbol{\mathrm{~s~}}$ and number $\boldsymbol{\mbox{k}}$.

Consider a substring $\boldsymbol{p}$ of string $\boldsymbol{\mathrm{~S~}}$. For each position of string $\boldsymbol{\mathrm{~S~}}$ mark it if there is an occurence of the substring that covers the position. More formally, position $\boldsymbol{i}$ will be marked if there exists such index $j$ that: $j\leq i\leq j+|p|-1$ and $s_js_{j+1}\cdots s_{j+|p|-1}=p$. We will tell $\boldsymbol{p}$ produce $\boldsymbol{x}$ islands if all the marked positions form $\boldsymbol{x}$ groups of contiguous positions.

For example, if we have a string ababaewabaq the substring aba marks the positions 1, 2, 3, 4, 5, 8, 9, 10; that is XXXXXewXXXq (X denotes marked position). We can see 2 groups of contiguous positions, that is 2 islands. Finally, substring aba produces 2 islands in the string ababaewabaq.

Calculate and print the number of different substrings of string $\boldsymbol{\mathrm{~S~}}$ that produce exactly $\boldsymbol{\mbox{k}}$ islands.

Input Format

The first line contains string $\boldsymbol{\mathrm{~S~}}$ $(1\leq|s|\leq10^5)$. The string consists of lowercase letters only. The second line contains an integer $\boldsymbol{\mbox{k}}$ $(1\leq k\leq|s|)$.

Output Format

Output a single integer $\textbf{z}$ the answer to the problem.

Sample Input
abaab
2

Sample Output
3

Explanation

All the suitable substrings are: a, ab, b.

见题面

见题面