问题描述

给定一个仅由小写字母构成的字符串 $s$，请你计算出其中满足以下条件的子串数量：

• 子串中所有字符出现次数均不超过 $k$ 次。

问有多少个子串满足条件。

输入格式

第一行输入一个字符串 $s$。

第二行输入一个整数 $k$。

$(1\le |s|,k\le 10^5)$

输出格式

第一行输出一个整数，表示满足条件的子串数量。

样例输入1

abacab
2

样例输出1

19