E. Intellectual Inquiry

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

After getting kicked out of her reporting job for not knowing the alphabet, Bessie has decided to attend school at the Fillet and Eggs Eater Academy. She has been making good progress with her studies and now knows the first k English letters.

Each morning, Bessie travels to school along a sidewalk consisting of m + n tiles. In order to help Bessie review, Mr. Moozing has labeled each of the first m sidewalk tiles with one of the first k lowercase English letters, spelling out a string t. Mr. Moozing, impressed by Bessie's extensive knowledge of farm animals, plans to let her finish labeling the last n tiles of the sidewalk by herself.

Consider the resulting string s (|s| = m + n) consisting of letters labeled on tiles in order from home to school. For any sequence of indices p1 < p2 < ... < pq we can define subsequence of the string s as string sp1sp2... spq. Two subsequences are considered to be distinct if they differ as strings. Bessie wants to label the remaining part of the sidewalk such that the number of distinct subsequencesof tiles is maximum possible. However, since Bessie hasn't even finished learning the alphabet, she needs your help!

Note that empty subsequence also counts.

Input

The first line of the input contains two integers n and k (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 26).

The second line contains a string t (|t| = m, 1 ≤ m ≤ 1 000 000) consisting of only first k lowercase English letters.

Output

Determine the maximum number of distinct subsequences Bessie can form after labeling the last n sidewalk tiles each with one of the first k lowercase English letters. Since this number can be rather large, you should print it modulo 109 + 7.

Please note, that you are not asked to maximize the remainder modulo 109 + 7! The goal is to maximize the initial value and then print the remainder.

INPUT

1 3
ac

output

8

input
0 2
aaba
output
10




Editorial of the match


For simplicity, let’s represent the letters by 1, 2, ..., k instead of actual characters. Let a[i] denote the number of distinct subsequences of the string that end in the letter i. Appending the letter j to a string only changes the value of a[j]. Note that the new a[j] becomes —we can have the single letter j, or append j to any of our old subsequences.

The key observation is that no matter what character j we choose to append, a[j] will always end up the same. This suggests a greedy algorithm—always appending the character j with the smallest a[j]. But how do we know which a[j] is minimal while maintaining their values modulo 109 + 7?

The final observation is that if the last occurrence of j is after the last occurrence of j' in our string, then a[j] > a[j']. This is true because appending j to the string makes a[j] larger than all other a[i]. So instead of choosing the minimum a[i], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in . Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity O((L + n)k).

                 ***************************HERE RUNS THE CODE***********************************



#include<bits/stdc++.h>

using namespace std;

int dp[2000010];

int occ[30];

int h[30];

#define mod 1000000007

int p2[2000010];

int n;

int k;

void pre()

{

    p2[0]=1;

    for(int i=1;i<=1000001;i++)

    p2[i]=(2*p2[i-1])%mod;

}

int findnext()

{

 /*  int mi=100000000;

   for(int i=0;i<k;i++)

   {

       if(h[i]<mi)

       mi=h[i];

   }

   //cout<<"mi "<<mi<<endl;

   int freq=0;

   for(int i=0;i<k;i++)

   {

        if(h[i]==mi)

        freq++;

   }*/

   int minpos=10000000;

   int ch;

   for(int i=0;i<k;i++)

   {

      //if(h[i]==mi)

     // {

          if(occ[i]<minpos)

    {

         minpos=occ[i];

      ch=i; 

    } 

 //   }

   }

   return ch;

}

int main()

{

 pre();

    cin>>n>>k;

 string s;

 cin>>s;

 memset(occ,-1,sizeof(occ));

 int m=s.length();

 dp[0]=1;

 for(int i=1;i<=m;i++)

 {

            dp[i]=2*dp[i-1];

        //    dp[i]++;

            dp[i]%=mod;

     if(occ[s[i-1]-'a']!=-1)

     {

         dp[i]-=dp[occ[s[i-1]-'a']-1];

      dp[i]+=mod;

      dp[i]%=mod; 

     }

     occ[s[i-1]-'a']=i; 

 }

// for(int i=1;i<=m;i++)

// cout<<dp[i]<<" ";

// cout<<endl;

 for(int i=0;i<m;i++)

 h[s[i]-'a']++;

 for(int i=m+1;i<=n+m;i++)

 {

 // cout<<"haire "<<endl;

            int ch=findnext();

   //     cout<<"hc "<<ch<<endl;

      dp[i]=dp[i-1]*2;

      dp[i]%=mod;

      if(occ[ch]!=-1)

      {

              dp[i]-=dp[occ[ch]-1];

        dp[i]+=mod;

        dp[i]%=mod; 

      }

      h[ch]++;

      occ[ch]=i; 

 }

// for(int i=1;i<=n+m;i++)

// cout<<dp[i]<<" ";

// cout<<endl;

 int ans=0;

    ans=dp[n+m];

 ans%=mod;

 cout<<ans<<endl;

 return 0;          

}