use std::io::prelude::*; fn main() { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); const KMAX: usize = 26; let mut tokens = input.split_ascii_whitespace(); let n = tokens.next().unwrap().parse::().unwrap(); let m = tokens.next().unwrap().parse::().unwrap(); let k = tokens.next().unwrap().parse::().unwrap(); let s = tokens.next().unwrap(); if n < 1 || n != s.len() || n > m || m > 500000 || k < 1 || k > KMAX { panic!(); } let mut kbits = 0u32; let mut dp = [MInt(0); KMAX]; let mut result = MInt(0); for c in s.bytes() { let mut ndp = [MInt(0); KMAX]; let ci = (c - b'a') as usize; if ci >= KMAX { panic!(); } for j in 0..ci { let kt = (kbits | (1 << j)).count_ones() - 1; ndp[kt as usize] += MInt(1); } kbits |= 1 << ci; if kbits.count_ones() >= (k as u32) { result += MInt(1); } for j in 1..KMAX { let je = dp[j - 1]; ndp[j - 1] += MInt(j as u32) * je; ndp[j] += MInt((KMAX - j) as u32) * je; } ndp[KMAX - 1] += MInt(KMAX as u32) * dp[KMAX - 1]; for &je in ndp[(k - 1)..KMAX].iter() { result += je; } dp = ndp; } if kbits.count_ones() >= (k as u32) { result -= MInt(1); } for _ in n..m { let mut ndp = [MInt(0); KMAX]; for j in 1..KMAX { let je = dp[j - 1]; ndp[j - 1] += MInt(j as u32) * je; ndp[j] += MInt((KMAX - j) as u32) * je; } ndp[KMAX - 1] += MInt(KMAX as u32) * dp[KMAX - 1]; for &je in ndp[(k - 1)..KMAX].iter() { result += je; } dp = ndp; } println!("{}", result.val()); } pub trait ModInt32Static { const MOD: u32; fn norm_impl(n: u32) -> u32; fn add_impl(lhs: u32, rhs: u32) -> u32; fn sub_impl(lhs: u32, rhs: u32) -> u32; fn mul_impl(lhs: u32, rhs: u32) -> u32; } macro_rules! modint32static_impl { ($modulus:literal, $st:ident) => { modint32static_impl!(@dol ($) $modulus, $st); }; (@dol ($dol:tt) $modulus:literal, $st:ident) => { #[derive(Copy, Clone)] pub struct $st(u32); impl ModInt32Static for $st { const MOD: u32 = ($modulus as u32); #[inline] fn norm_impl(x: u32) -> u32 { x % Self::MOD } #[inline] fn add_impl(lhs: u32, rhs: u32) -> u32 { let v = u64::from(lhs) + u64::from(rhs); match v.checked_sub(u64::from(Self::MOD)) { None => v as u32, Some(w) => w as u32, } } #[inline] fn sub_impl(lhs: u32, rhs: u32) -> u32 { let (v, f) = lhs.overflowing_sub(rhs); v.wrapping_add(u32::from(f).wrapping_neg() & Self::MOD) } #[inline] fn mul_impl(lhs: u32, rhs: u32) -> u32 { (u64::from(lhs) * u64::from(rhs) % u64::from(Self::MOD)) as u32 } } impl std::ops::Add for $st { type Output = Self; #[inline] fn add(self, rhs: Self) -> Self::Output { $st($st::add_impl(self.0, rhs.0)) } } impl std::ops::Sub for $st { type Output = Self; #[inline] fn sub(self, rhs: Self) -> Self::Output { $st($st::sub_impl(self.0, rhs.0)) } } impl std::ops::Mul for $st { type Output = Self; #[inline] fn mul(self, rhs: Self) -> Self::Output { $st($st::mul_impl(self.0, rhs.0)) } } impl std::ops::Neg for $st { type Output = Self; #[inline] fn neg(self) -> Self::Output { $st($st::sub_impl(0, self.0)) } } impl std::ops::AddAssign for $st { #[inline] fn add_assign(&mut self, rhs: Self) { *self = Self(Self::add_impl(self.0, rhs.0)); } } impl std::ops::SubAssign for $st { #[inline] fn sub_assign(&mut self, rhs: Self) { *self = Self(Self::sub_impl(self.0, rhs.0)); } } impl std::ops::MulAssign for $st { #[inline] fn mul_assign(&mut self, rhs: Self) { *self = Self(Self::mul_impl(self.0, rhs.0)); } } impl $st { #[inline] pub fn new(n: u32) -> Self { Self(Self::norm_impl(n)) } #[inline] pub fn val(&self) -> u32 { self.0 } } }; } modint32static_impl!(998244353, MInt);