/*rabin-karp算法基本思想是：把该字符集当成一个整数来看待比较字符串转化的整数来判断两个字符串是否相等对于这个题目，有几个疑问，N如果很大，那么int不就超了嘛，可是却能AC.理论上 应该去摸一个大质数的*/// include file#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        using namespace std;// typedeftypedef long long LL;typedef unsigned long long ULL;// #define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)#define FORi(a,b,c) for(int i=(a);i<(b);i+=c)#define FORj(a,b,c) for(int j=(a);j<(b);j+=c)#define FORk(a,b,c) for(int k=(a);k<(b);k+=c)#define FORp(a,b,c) for(int p=(a);p<(b);p+=c)#define FF(i,a) for(int i=0;i<(a);i+++)#define FFD(i,a) for(int i=(a)-1;i>=0;i--)#define Z(a) (a<<1)#define Y(a) (a>>1)const double eps = 1e-6;const double INFf = 1e10;const int INFi = 1000000000;const double Pi = acos(-1.0);template
                        
                          inline T sqr(T a){return a*a;}template
                         
                           inline T TMAX(T x,T y){ if(x>y) return x; return y;}template
                          
                            inline T TMIN(T x,T y){ if(x
                           
                             inline void SWAP(T &x,T &y){ T t = x; x = y; y = t;}template
                            
                              inline T MMAX(T x,T y,T z){ return TMAX(TMAX(x,y),z);}// code begin#define MAXN 16000001int N,NC;char in[20000000];int len;bool hash[MAXN];int asc[300];int ans;// string search algorithmvoid SSA_Rabin_Karp(){ memset(hash,0,sizeof(hash)); int cur = 0; int first = 1; FORi(0,N,1) { cur = cur*NC+asc[in[i]]; first = first*NC; } first = first/NC; // FORi(0,len-N+1,1) { if(!hash[cur]) { hash[cur]=true; ans++; } if(i+N>=len) break; cur = (cur - asc[in[i]]*first)*NC+asc[in[i+N]]; }}int main(){ read; write; while(scanf("%d %d",&N,&NC)!=-1) { //此处是NC进制 scanf("%s",in); // 首先把相应的字符对应于一个0~NC-1 int id = 0; len = strlen(in); memset(asc,-1,sizeof(asc)); FORi(0,len,1) { if(asc[in[i]]==-1) asc[in[i]] = id++; } // ans = 0; SSA_Rabin_Karp(); printf("%d\n",ans); } return 0;}