Merkkijonot

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;

ll powmod(ll a, ll p, ll modd) {
	if (p==0) return 1;
	if (p%2==0) {
		a=powmod(a, p/2, modd);
		return (a*a)%modd;
	}
	return (a*powmod(a, p-1, modd))%modd;
}
ll invp(ll a, ll p) {
	return powmod(a, p - 2, p);
}
vector<ll> solve(vector<ll> S, ll mod) {
	vector<ll> C = {1};
	vector<ll> B = {1};
	ll L = 0;ll m = 1;ll b = 1;ll N = S.size();
	for (ll i = 0; i < N; i++) {
		ll d = S[i];
		for (ll j = 1; j <= L; j++) {
			d += C[j]*S[i - j];d %= mod;
		}
		if (d == 0) {
			m++;
		} else if (2*L <= i) {
			vector<ll> T = C;
			ll a = (invp(b, mod)*d)%mod;
			for (int j=0;j<i+1-2*L;j++) {
				C.push_back(0);
			}
			L=i+1-L;
			for (ll j = m; j <= L; j++) {
				C[j] -= a*B[j - m];C[j] %= mod;
			}
			B = T;b = d;m = 1;
		} else {
			ll a = (invp(b, mod)*d)%mod;
			for (ll j = m; j < m+(int)B.size(); j++) {
				C[j] -= a*B[j - m];C[j] %= mod;
			}
			m++;
		}
	}
	for (ll i = 0; i <= L; i++) {
		C[i] += mod;C[i] %= mod;
	}
	return C;
}
struct LinearRecurrence {
	vector<vector<ll> > mat;
	vector<ll> seq;
	ll mod;
	vector<vector<ll> > mul(vector<vector<ll> > a, vector<vector<ll> > b) {
		int n=(int)a.size();
		vector<vector<ll> > ret(n);
		for (int i=0;i<n;i++){
			ret[i].resize(n);
			for (int j=0;j<n;j++){
				ret[i][j]=0;
				for (int k=0;k<n;k++){
					ret[i][j]+=a[i][k]*b[k][j];
					ret[i][j]%=mod;
				}
			}
		}
		return ret;
	}
	vector<vector<ll> > pot(vector<vector<ll> > m, ll p) {
		if (p==1) return m;
		if (p%2==0) {
			m=pot(m, p/2);
			return mul(m, m);
		}
		else {
			return mul(m, pot(m, p-1));
		}
	}
	ll get(ll index) {
		if (index<(ll)mat.size()) {
			return seq[index];
		}
		vector<vector<ll> > a=pot(mat, index-(ll)mat.size()+1);
		ll v=0;
		for (int i=0;i<(int)mat.size();i++) {
			v+=a[0][i]*seq[(int)mat.size()-i-1];
			v%=mod;
		}
		return v;
	}
	LinearRecurrence(vector<ll> S, ll mod_) {
		seq=S;
		mod=mod_;
		vector<ll> C=solve(S, mod);
		int n=(int)C.size()-1;
		cerr<<"found "<<n<<endl;
		assert(n<=100);
		mat.resize(n);
		for (int i=0;i<n;i++) {
			mat[i].resize(n);
		}
		for (int i=0;i<n;i++) {
			mat[0][i]=(mod-C[i+1])%mod;
		}
		for (int i=1;i<n;i++) {
			mat[i][i-1]=1;
		}
	}
};


const ll mod=1e9+7;

int m;
string s;

ll go(ll t, char c){
	if (t==0) return 0;
	ll ne=0;
	if (c==s[0]) {
		ne|=2ll;
	}
	for (ll i=0;i<(ll)m;i++){
		if ( ( ( ((1ll<<i) + (1ll<<m)) & t) != 0) && s[i]==c){
			ne|=(1ll<<(i+1ll));
		}
	}
	return ne;
}

string bp(ll t, int bs){
	string r;
	for (ll i=0;i<(ll)bs;i++){
		if (t & (1ll<<i)){
			r+='1';
		} else {
			r+='0';
		}
	}
	return r;
}

map<ll,ll> dp[1010];

int main(){
	int n;
	cin>>n>>m>>s;
	if (m>n){
		cout<<0<<endl;
		return 0;
	}
	dp[0][1]=1;
	vector<ll> ans(1000-m);
	for (int i=0;i<1000;i++){
		for (auto tt : dp[i]){
			if (i>=m && (tt.F & (1ll<<m))){
				ans[i-m]+=tt.S;
				ans[i-m]%=mod;
			}

			for (char c='a';c<='z';c++){
				ll nt=go(tt.F, c);
				if (nt==0) continue;
				dp[i+1][nt] += tt.S;
				dp[i+1][nt]%=mod;
			}
		}
	}

	LinearRecurrence lr(ans, mod);
	if (n<1000){
		assert(ans[n-m] == lr.get(n-m));
	}
	cout<<lr.get(n-m)<<endl;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 1

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 21

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 1

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 10

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 11

Test 6

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 10

Test 7

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 1

Test 8

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 16

Test 9

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 8

Test 10

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

found 10

Test 11

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 1

Test 12

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 52

Test 13

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 54

Test 14

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 52

Test 15

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 1

Test 16

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 96

Test 17

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 24

Test 18

Group: 2, 3, 4, 5

Verdict: ACCEPTED

found 50

Test 19

Group: 3, 4, 5

Verdict: ACCEPTED

found 1

Test 20

Group: 3, 4, 5

Verdict: ACCEPTED

found 59

Test 21

Group: 3, 4, 5

Verdict: ACCEPTED

found 55

Test 22

Group: 3, 4, 5

Verdict: ACCEPTED

found 52

Test 23

Group: 3, 4, 5

Verdict: ACCEPTED

found 1

Test 24

Group: 3, 4, 5

Verdict: ACCEPTED

found 96

Test 25

Group: 3, 4, 5

Verdict: ACCEPTED

found 24

Test 26

Group: 3, 4, 5

Verdict: ACCEPTED

found 50

Test 27

Group: 4, 5

Verdict: ACCEPTED

found 1

Test 28

Group: 4, 5

Verdict: ACCEPTED

found 50

Test 29

Group: 4, 5

Verdict: ACCEPTED

found 56

Test 30

Group: 4, 5

Verdict: ACCEPTED

found 52

Test 31

Group: 4, 5

Verdict: ACCEPTED

found 1

Test 32

Group: 4, 5

Verdict: ACCEPTED

found 96

Test 33

Group: 4, 5

Verdict: ACCEPTED

found 24

Test 34

Group: 4, 5

Verdict: ACCEPTED

found 50

Test 35

Group: 5

Verdict: ACCEPTED

found 1

Test 36

Group: 5

Verdict: ACCEPTED

found 54

Test 37

Group: 5

Verdict: ACCEPTED

found 54

Test 38

Group: 5

Verdict: ACCEPTED

found 52

Test 39

Group: 5

Verdict: ACCEPTED

found 1

Test 40

Group: 5

Verdict: ACCEPTED

found 96

Test 41

Group: 5

Verdict: ACCEPTED

found 24

Test 42

Group: 5

Verdict: ACCEPTED

found 50