Untitled

#include <bits/stdc++.h>

using namespace std;

#define TASK "lpd"

#define X first
#define Y second

typedef pair<int, int> ii;

const int M = 1e9+7;
const int N = 333;

int Next[N][3];
int dp[N][N][N][3];

string s;
string pref_str[N];

void inc(int& v, int adder){
	v += adder;
	v %= M;
}

int prefix_equal_suffix(string a, string b){
	int len = b.length();
	for(int res = len; res >= 0; res--){
		if(pref_str[res] == b) return res;
		b.erase(0, 1);
	}
}

main(){
	#ifndef ONLINE_JUDGE
	freopen(TASK".inp","r",stdin);
	freopen(TASK".out","w",stdout);
	#endif
	int n, m, slen;
	cin >> n >> m >> slen;
	cin >> s;

	pref_str[0] = "";
	for(int pref = 1; pref <= slen; pref++){
		pref_str[pref] = pref_str[pref-1];
		pref_str[pref] += s[pref-1];
	}

	string t = "";
	for(int pref = 0; pref <= slen; pref++){
		if(pref) t += s[pref-1];
		Next[pref][0] = prefix_equal_suffix(s, t + 'L');
		Next[pref][1] = prefix_equal_suffix(s, t + 'P');
		Next[pref][2] = prefix_equal_suffix(s, t + 'D');
	}

	dp[0][0][0][0] = 1;
	for(int len = 0; len < n; len++)
		for(int nl = 0; nl <= len; nl++)
			for(int pref = 0; pref <= slen; pref++)
				for(int have = 0; have < 2; have++){
					if(!dp[len][nl][pref][have]) continue;
					// choose l
					int new_pref = Next[pref][0];
					int new_have = have | (new_pref == slen);
					inc(dp[len+1][nl+1][new_pref][new_have], dp[len][nl][pref][have]);
					// choose p
					new_pref = Next[pref][1];
					new_have = have | (new_pref == slen);
					inc(dp[len+1][nl][new_pref][new_have], dp[len][nl][pref][have]);
					// choose d
					new_pref = Next[pref][2];
					new_have = have | (new_pref == slen);
					inc(dp[len+1][nl][new_pref][new_have], dp[len][nl][pref][have]);
				}

	int ans = 0;
	for(int nl = m; nl <= n; nl++)
		for(int i = 0; i <= slen; i++)
			inc(ans, dp[n][nl][i][0]);
	cout << ans;
}