Недавно Norge нашел строку \(s = s_1 s_2 \ldots s_n\), состоящую из \(n\) строчных букв латинского алфавита. В качестве упражнения для улучшения скорости печатания он решил напечатать все подстроки \(s\). Да, все \(\frac{n (n + 1)}{2}\) из них!
Подстрокой строки \(s\) называется непустая строка \(x = s[a \ldots b] = s_{a} s_{a + 1} \ldots s_{b}\) (\(1 \leq a \leq b \leq n\)). Например, «auto» и «ton» являются подстроками «automaton».
Незадолго до начала упражнения Norge осознал, что его клавиатура сломана, а если говорить более точно, он может использовать только \(k\) латинских букв \(c_1, c_2, \ldots, c_k\) из \(26\).
После этого Norge стало интересно, как много подстрок строки \(s\) он сможет написать, используя свою сломанную клавиатуру. Помогите ему найти это число.
Выходные данные
Выведите одно целое число — количество подстрок \(s\), которые можно написать, используя только доступные буквы \(c_1, c_2, \ldots, c_k\).
Примечание
В первом примере Norge может напечатать подстроки \(s[1\ldots2]\), \(s[2\ldots3]\), \(s[1\ldots3]\), \(s[1\ldots1]\), \(s[2\ldots2]\), \(s[3\ldots3]\), \(s[5\ldots6]\), \(s[6\ldots7]\), \(s[5\ldots7]\), \(s[5\ldots5]\), \(s[6\ldots6]\), \(s[7\ldots7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
abacaba
a b
|
12
|
|
2
|
10 3
sadfaasdda
f a d
|
21
|
|
3
|
7 1
aaaaaaa
b
|
0
|