#include #include #define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++) #define rep(i, n) rep2(i, 0, n) #define all(x) begin(x), end(x) #ifdef ENV_LOCAL #define dump \ if (1) cerr #else #define dump \ if (0) cerr #endif using namespace std; using namespace std::string_literals; using i32 = int32_t; using i64 = int64_t; using f64 = double; using f80 = long double; using vi32 = vector; using vi64 = vector; /* * harudake::modint * * Copyright (c) 2021 prime number * * This software is released under the MIT license. * see https://opensource.org/licenses/MIT * */ namespace harudake { template class static_modint; using modint_1000000007 = static_modint; using modint_998244353 = static_modint; template static_modint add(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val + rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint::make_raw(tmp); } template static_modint sub(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val + MOD - rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint::make_raw(tmp); } template static_modint mul(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val * rhs.val; tmp %= MOD; return static_modint::make_raw(tmp); } // data types must be signed integer inline int64_t inv(const int64_t a, const int64_t p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); }; template static_modint div(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val * inv(rhs.val, MOD); tmp %= MOD; return static_modint::make_raw(tmp); } template static_modint pow(const static_modint base, const uint64_t index) { if (index == 0) return static_modint{1}; if (index % 2 == 1) { return pow(base, index - 1) * base; } else { auto half = pow(base, index / 2); return half * half; } } template class static_modint { using modint = static_modint; public: static constexpr base_t mod = MOD; static_modint() : val(0) {} static_modint(const base_t x) : val(x % MOD) {} static_modint(const modint&) = default; modint& operator=(const modint&) = default; modint& operator=(const base_t x) { val = x % MOD; return *this; } modint operator-() const { return val == 0 ? 0 : MOD - val; } explicit operator base_t() const { return val; } base_t get() const { return val; } constexpr base_t get_mod() const { return mod; } static modint make_raw(const base_t raw) { modint res; res.val = raw; return res; } private: friend modint add(const modint, const modint); friend modint sub(const modint, const modint); friend modint mul(const modint, const modint); friend modint div(const modint, const modint); base_t val; }; template static_modint operator+(const static_modint lhs, const static_modint rhs) { return add(lhs, rhs); } template static_modint operator-(const static_modint lhs, const static_modint rhs) { return sub(lhs, rhs); } template static_modint operator*(const static_modint lhs, const static_modint rhs) { return mul(lhs, rhs); } template static_modint operator/(const static_modint lhs, const static_modint rhs) { return div(lhs, rhs); } template static_modint operator^(const static_modint lhs, const uint64_t rhs) { return pow(lhs, rhs); } template static_modint& operator+=(static_modint& lhs, const static_modint rhs) { return lhs = lhs + rhs; } template static_modint& operator-=(static_modint& lhs, const static_modint rhs) { return lhs = lhs - rhs; } template static_modint& operator*=(static_modint& lhs, const static_modint rhs) { return lhs = lhs * rhs; } template static_modint& operator/=(static_modint& lhs, const static_modint rhs) { return lhs = lhs / rhs; } template static_modint& operator^=(static_modint& lhs, const uint64_t rhs) { return lhs = lhs ^ rhs; } } // namespace harudake using namespace harudake; using modint = modint_998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i64 n, m, k; cin >> n >> m >> k; string s; cin >> s; modint ans(0); set cs; vector dp(27); rep(i, m) { vector nxt(27); if (i < n) { rep2(ch, 'a', s[i]) { i64 idx = ch - 'a'; if (cs.count(ch)) { nxt[size(cs)] += modint(1); } else { nxt[size(cs) + 1] += modint(1); } } cs.insert(s[i]); if (i < n - 1 && size(cs) >= k) { ans += modint(1); } } rep(j, 27) { nxt[j] += dp[j] * modint(j); if (j < 26) { nxt[j + 1] += dp[j] * modint(26 - j); } } rep(j, 27) { if (j >= k) { ans += nxt[j]; } } swap(dp, nxt); } cout << ans.get() << endl; return 0; }