use std::io::prelude::*; fn main() { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); const MOD: u64 = 998244353; const KMAX: usize = 26; const KMAX2: usize = KMAX + 2; 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 kbc = 0usize; let mut dp = [0u64; KMAX2]; let mut result = 0u64; for c in s.bytes() { let mut ndp = [0u64; KMAX2]; let ci = (c - b'a') as usize; if ci >= KMAX { panic!(); } let same = (kbits & ((1 << ci) - 1)).count_ones() as u64; ndp[kbc] += same; ndp[kbc + 1] += (ci as u64) - same; if (kbits & (1 << ci)) == 0 { kbits |= 1 << ci; kbc += 1; } if kbc >= k { result += 1; } for j in 1..=KMAX { ndp[j] += (j as u64) * dp[j]; ndp[j + 1] += ((KMAX - j) as u64) * dp[j]; ndp[j] %= MOD; } for &je in ndp[k..=KMAX].iter() { result += je; } dp = ndp; } if kbc >= k { result -= 1; } for _ in n..m { let mut ndp = [0u64; KMAX2]; for j in 1..=KMAX { ndp[j] += (j as u64) * dp[j]; ndp[j + 1] += ((KMAX - j) as u64) * dp[j]; ndp[j] %= MOD; } for &je in ndp[k..=KMAX].iter() { result += je; } dp = ndp; } result %= MOD; println!("{}", result); }