#pragma GCC optimize ("O3") #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx") #include // array, swap #include // (C++20) popcount #include // abort #include // cin, cout, endl #include // string #define MOD 998244353 #define KMAX 26 #define KMAX2 (KMAX+2) using ull = unsigned long long; int main() { ull n, m, k; std::string s; std::cin >> n >> m >> k >> s; if(n < 1 || n > m || m > 500000 || s.length() != n || k < 1 || k > KMAX) { std::abort(); } ull kbits = 0, kbc = 0, result = 0; std::array dp, ndp; dp.fill(0); for(auto it = s.begin(); it != s.end(); it++) { ull ci = *it - 'a'; if(ci >= KMAX) { std::abort; } ndp.fill(0); ull same = std::popcount(kbits & ((1 << ci) - 1)); ndp[kbc] += same; ndp[kbc + 1] += ci - same; if((kbits & (1 << ci)) == 0) { kbits |= (1 << ci); kbc += 1; } if(kbc >= k) { result += 1; } for(ull j = 1; j <= KMAX; j++) { ndp[j] += j * dp[j]; ndp[j + 1] += (KMAX - j) * dp[j]; ndp[j] %= MOD; } for(ull j = k; j <= KMAX; j++) { result += ndp[j]; } dp.swap(ndp); } if(kbc >= k) { result -= 1; } for(ull i = n; i < m; i++) { ndp.fill(0); for(ull j = 1; j <= KMAX; j++) { ndp[j] += j * dp[j]; ndp[j + 1] += (KMAX - j) * dp[j]; ndp[j] %= MOD; } for(ull j = k; j <= KMAX; j++) { result += ndp[j]; } dp.swap(ndp); } result %= MOD; std::cout << result << std::endl; }