#include // array, swap #include // (C++20) popcount #include // abort #include // cin, cout, endl #include // string #define MOD 998244353 #define KMAX 26 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, 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); for(ull j = 0; j < ci; j++) { ndp[std::popcount(kbits | (1 << j)) - 1] += 1; } kbits |= (1 << ci); if(std::popcount(kbits) >= k) { result += 1; } for(ull j = 1; j < KMAX; j++) { ndp[j - 1] += j * dp[j - 1]; ndp[j] += (KMAX - j) * dp[j - 1]; } ndp[KMAX - 1] += KMAX * dp[KMAX - 1]; for(ull j = 0; j < KMAX; j++) { ndp[j] %= MOD; } for(ull j = k - 1; j < KMAX; j++) { result += ndp[j]; } result %= MOD; std::swap(dp, ndp); } if(std::popcount(kbits) >= k) { result = (result + (MOD - 1)) % MOD; } for(ull i = n; i < m; i++) { ndp.fill(0); for(ull j = 1; j < KMAX; j++) { ndp[j - 1] += j * dp[j - 1]; ndp[j] += (KMAX - j) * dp[j - 1]; } ndp[KMAX - 1] += KMAX * dp[KMAX - 1]; for(ull j = 0; j < KMAX; j++) { ndp[j] %= MOD; } for(ull j = k - 1; j < KMAX; j++) { result += ndp[j]; } result %= MOD; std::swap(dp, ndp); } std::cout << result << std::endl; }