1770 - 子段统计
Description

给定一个字符串S,只由26 种小写字母组成。现在给定一个长度L,要求统计一下S有多少种不同的长度为L的子串(S中连续的几个字符)。

Input

第一行两个整数 L 和K 。( L≥1, 1≤K≤26,K^L≤2×10^7

第二行一个字符串 S。( 1≤|S|≤1000000)


Output

输出一个整数表示答案。

Examples

Input

1 2
ababab

Output

2
题目参数
Time Limit 5 seconds
Memory Limit 1024 MB
提交次数 29
通过次数 0