#include #define rep(i, s, f) for(ll i = s; i <= f; i++) #define per(i, s, f) for(ll i = s; i >= f; i--) #define vvvl vector>> #define vvl vector> #define vl vector #define ENDL '\n' typedef long long ll; using namespace std; ////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //グローバル変数を置くところ(情報工学意識高め) ll int_max = 1001001001; ll ll_max = 1001001001001001001; const double pi = 3.141592653589793; vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1}; //cout << fixed << setprecision(10); //#pragma GCC optimize ("-O3") //ll mod = 1000000007; ll mod = 998244353; ll N, M, K; string S; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ll solve1() { vvvl dp(M+1, vvl(2, vl(28, 0))); dp.at(0).at(1).at(0) = 1; /* dp[i][1][k] := 長さがi,使った文字の種類がkでかつ辞書順でSより小さいことが確定していない文字列の総数 = 長さがiでSのi文字目までと一致する文字列の総数 dp[i][0][k] := 長さがi,使った文字の種類がkでかつ辞書順でSより小さいことが確定している文字列の総数 */ vl used(27, false);//これまで見たSの中で、どの文字が使われているか ll kind = 0; //これまで見たSの中に入っている文字の種類数 for(int i = 1; i <= N; i++) { ll cnt = 0; ll kind_small = 0; ll now = S.at(i-1) - 'a' + 1; for (int j = 1; j <= now - 1; j++) { if(used.at(j) == false) cnt++;//Sのi文字目より小さい && 出現したことがない文字の種類数 else kind_small++;//Sのi文字目より小さい && 出現したことがある文字の種類数 } /*Sと一致する文字列からの遷移*///----------------------------------------------------------- dp.at(i).at(0).at(kind) += kind_small * dp.at(i-1).at(1).at(kind);//使ったことある本家より小さいやつを末尾につける dp.at(i).at(0).at(kind) %= mod; dp.at(i).at(0).at(kind+1) += cnt * dp.at(i-1).at(1).at(kind);//使ったことない本家より小さいやつを末尾につける dp.at(i).at(0).at(kind+1) %= mod; //---------------------------------------------------------------------------------------- if(!used.at(now)) kind++; dp.at(i).at(1).at(kind) = 1; used.at(now) = true; //Sを見たので更新 /*Sより小さいことが確定しているものからの遷移*///----------------------------------------------- for (int j = 0; j <= 26; j++) { dp.at(i).at(0).at(j) += dp.at(i-1).at(0).at(j) * j;//末尾に使用済みをつける  dp.at(i).at(0).at(j) %= mod; if(j == 0) continue; dp.at(i).at(0).at(j) += dp.at(i-1).at(0).at(j-1) * (26 - (j-1)); //末尾に使ったことないやつをつける dp.at(i).at(0).at(j) %= mod; } //-------------------------------------------------------------------------------------- } //長さがNの時点でSと一致しているならば、その後何をつけてもSより辞書順が小さくなることはない for (int i = N+1; i <= M; i++) { for (int j = 0; j <= 26; j++) { dp.at(i).at(0).at(j) += dp.at(i-1).at(0).at(j) * j;//末尾に使用済みをつける  dp.at(i).at(0).at(j) %= mod; if(j == 0) continue; dp.at(i).at(0).at(j) += dp.at(i-1).at(0).at(j-1) * (26 - (j-1)); //末尾に使ったことないやつをつける dp.at(i).at(0).at(j) %= mod; } } ll ans = 0; for (int i = 0; i <= M; i++) { for (int j = K; j <= 26; j++) { ans += dp.at(i).at(0).at(j); ans %= mod; if(i < N) { ans += dp.at(i).at(1).at(j); ans %= mod; } } } return ans; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cin >> N >> M >> K; cin >> S; cout << solve1() << endl; } //if(S.at(i) == 1 ← 笑) // modは取りましたか...?(´・ω・`)