#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; bool printb(bool f) { if (f)printf("Yes\n"); else printf("No\n"); return f; } template void prt(T t = "", string sep = "\n") { cout << t << sep; return; } template void printl(vector a, string sep = " ") { for (int i = 0; i < a.size(); i++) { cout << a[i]; if (i != a.size() - 1)cout << sep; } if (sep != "\n")cout << "\n"; return; } bool prt_isfixed = false; template void prt_fix(T t, string sep = "\n") { if (!prt_isfixed) { cout << fixed << setprecision(15); prt_isfixed = true; } prt(t, sep); } #define all(a) a.begin(),a.end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) using uint = unsigned int; using llong = long long; using ullong = unsigned long long; using pii = pair; using pll = pair; using pli = pair; using pil = pair; template using vec2 = vector>; template inline bool chmin(T& a, T b) { return (a > b) ? (a = b, true) : false; } template inline bool chmax(T& a, T b) { return (a < b) ? (a = b, true) : false; } bool bitIn(llong a, int b) { return ((a >> b) & 1); } int bitCnt(llong a) { int re = 0; while (a > 0) { if (a & 1)re++; a >>= 1; } return re; } llong powL(llong n, llong i) { llong re = 1; while (i >= 1) { if (i & 1) re *= n; n *= n; i >>= 1; } return re; } llong powL_M(llong n, llong i, llong mod) { llong re = 1; while (i >= 1) { if (i & 1) { re *= n; re %= mod; } n *= n; n %= mod; i >>= 1; } return re; } int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }; int dx8[8] = { 0,1,1,1,0,-1,-1,-1 }, dy8[8] = { -1,-1,0,1,1,1,0,-1 }; /* modintクラス。四則演算と累乗が定義されている。 割り算はmodが素数でない時にも使える。(逆元の存在条件注意) extGCD(),GCD()を含む */ template T extGCD(T a, T b, T& x, T& y) { if (b == 0) { x = 1; y = 0; return a; } T gcd = extGCD(b, a % b, y, x); y -= a / b * x; return gcd; } template T GCD(T a, T b) { T x, y; return extGCD(a, b, x, y); } static const int mod = 998244353; //問題文に合わせて変更すること class modint { public: long long x; modint(long long x = 0) :x((x% mod + mod) % mod) {} modint operator-() const { return (-x); } modint& operator+=(const modint& a) { if ((x += a.x) >= mod)x -= mod; return *this; } modint& operator-=(const modint& a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } modint& operator*=(const modint& a) { (x *= a.x) %= mod; return *this; } modint operator+(const modint& a) const { modint res(*this); return res += a; } modint operator-(const modint& a) const { modint res(*this); return res -= a; } modint operator*(const modint& a) const { modint res(*this); return res *= a; } modint inv() const { long long y, c; extGCD(x, (long long)mod, y, c); return y; } modint& operator/=(const modint& a) { return (*this) *= a.inv(); } modint operator/ (const modint& a) const { modint res(*this); return res /= a; } friend ostream& operator<<(ostream& os, const modint& a) { os << a.x; return os; } }; //pow(a , n) modint型aのn乗のmodを求める template modint powM(modint a, T n) { modint re(1); while (n > 0) { if (n & 1)re *= a; a *= a; n >>= 1; } return re; } modint sum_numM(modint l, modint r) { return (l + r) * (r - l + 1) / 2; } int main() { int n, m, k; cin >> n >> m >> k; string s; cin >> s; vector dp(m + 1, vector(27, 0)); //dp[i][j]=i文字目まで決めてj種類の文字を使ってて、辞書順でsよりも小さいようなもの vector isUsed(27,false); //sのi文字までに使われているか int cnt = 0; modint re; for (int i = 1; i <= m; i++) { if (i <= n) { for (int j = 0; j < s[i-1]-'a'; j++) { if (isUsed[j])dp[i][cnt] += 1; else dp[i][cnt + 1] += 1; } if (cnt >= k)re+=1; if (!isUsed[s[i - 1] - 'a']) { isUsed[s[i - 1] - 'a'] = true; cnt++; } } for (int j = 1; j < 27; j++) { dp[i][j] += dp[i - 1][j - 1] * (26 - j + 1); dp[i][j] += dp[i - 1][j] * j; } } //for (auto i : dp)printl(i); for (int i = 1; i <= m; i++) { for (int j = k; j < 27;j++) { re += dp[i][j]; } } prt(re); }