#![allow(unused_macros)] #![allow(dead_code)] #![allow(unused_imports)] // # ファイル構成 // - use 宣言 // - lib モジュール // - main 関数 // - basic モジュール // // 常に使うテンプレートライブラリは basic モジュール内にあります。 // 問題に応じて使うライブラリ lib モジュール内にコピペしています。 // ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder // Twitter はこちら → https://twitter.com/RheoTommy use std::collections::*; use std::io::{stdout, BufWriter, Write}; use crate::basic::*; use crate::lib::*; pub mod lib { pub type ModInt = StaticModInt; pub const MOD: i32 = MOD998244353; pub const MOD1000000007: i32 = 1000000007; pub const MOD998244353: i32 = 998244353; #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)] pub struct StaticModInt(i32); impl std::fmt::Display for StaticModInt { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::fmt::Debug for StaticModInt { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self) } } impl StaticModInt { pub fn new>(n: T) -> Self { n.into() } fn new_inner(n: i32) -> Self { Self(n) } pub fn pow>(self, n: T) -> Self { let n: Int = n.into(); let mut n = n.0; assert!(n >= 0); let mut res = StaticModInt::new(1); let mut x = self; while n != 0 { if n & 1 == 1 { res *= x; } n /= 2; x *= x; } res } pub fn inv(self) -> Self { self.pow((MOD - 2) as u64) } } impl> From for StaticModInt { fn from(t: T) -> Self { let n: Int = t.into(); let n = (n.0 % MOD as i64) as i32; if n < 0 { Self::new_inner(n + MOD) } else { Self::new_inner(n) } } } impl> std::ops::Add for StaticModInt { type Output = Self; fn add(self, rhs: T) -> Self::Output { let mut tmp = self.0; let t: StaticModInt = rhs.into(); tmp += t.0; if tmp >= MOD { tmp -= MOD; } debug_assert!((0..MOD).contains(&tmp)); Self(tmp) } } impl> std::ops::AddAssign for StaticModInt { fn add_assign(&mut self, rhs: T) { *self = *self + rhs.into() } } impl> std::ops::Sub for StaticModInt { type Output = Self; fn sub(self, rhs: T) -> Self::Output { let mut tmp = self.0; let t: StaticModInt = rhs.into(); tmp -= t.0; if tmp < 0 { tmp += MOD; } debug_assert!((0..MOD).contains(&tmp)); Self(tmp) } } impl> std::ops::SubAssign for StaticModInt { fn sub_assign(&mut self, rhs: T) { *self = *self - rhs.into(); } } impl> std::ops::Mul for StaticModInt { type Output = Self; fn mul(self, rhs: T) -> Self::Output { let mut tmp = self.0 as i64; let t: StaticModInt = rhs.into(); tmp *= t.0 as i64; if tmp >= MOD as i64 { tmp %= MOD as i64; } let tmp = tmp as i32; debug_assert!((0..MOD).contains(&tmp)); Self(tmp) } } impl> std::ops::MulAssign for StaticModInt { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs.into(); } } impl> std::ops::Div for StaticModInt { type Output = Self; fn div(self, rhs: T) -> Self::Output { let t: StaticModInt = rhs.into(); self * t.inv() } } impl> std::ops::DivAssign for StaticModInt { fn div_assign(&mut self, rhs: T) { *self = *self / rhs.into(); } } /// 二項係数を高速に計算するテーブルを作成する /// 構築 O(N) /// クエリ O(1) /// メモリ O(N) pub struct CombTable { fac: Vec, f_inv: Vec, } impl CombTable { /// O(N)で構築 pub fn new>(n: T) -> Self { let n: Int = n.into(); assert!(n.0 >= 0); let n = n.0 as usize; let mut fac = vec![ModInt::new(1); n + 1]; let mut f_inv = vec![ModInt::new(1); n + 1]; let mut inv = vec![ModInt::new(1); n + 1]; inv[0] = ModInt::new(0); for i in 2..=n { fac[i] = fac[i - 1] * i; inv[i] = ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32); f_inv[i] = f_inv[i - 1] * inv[i]; } Self { fac, f_inv } } /// nCkをO(1)で計算 pub fn comb, T2: Into>(&self, n: T1, k: T2) -> ModInt { let n: Int = n.into(); let k: Int = k.into(); assert!(n.0 >= 0); assert!(k.0 >= 0); let n = n.0 as usize; let k = k.0 as usize; if n < k { return ModInt::new(0); } self.fac[n] * (self.f_inv[k] * self.f_inv[n - k]) } } #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)] pub struct Int(pub i64); macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; } impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize); macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; } impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize); } fn main() { let mut io = IO::new(); let n = io.next_usize(); let s = io.next_chars().collect::>(); let mut dp = vec![HashSet::new(); n]; for i in 0..n { if s[i] == '?' { for c in 'a'..='z' { dp[i].insert(c); } } else { dp[i].insert(s[i]); } } for i in 0..n - 1 { let j = i + 1; if s[i] != '?' { dp[j].remove(&s[i]); } if s[j] != '?' { dp[i].remove(&s[j]); } } for center in 1..n - 1 { let l = center - 1; let r = center + 1; if s[l] != '?' { dp[r].remove(&s[l]); } if s[r] != '?' { dp[l].remove(&s[r]); } } let mut dp = dp.into_iter().map(|hm| hm.len()).collect::>(); // eprintln!("{:?}", dp); for i in 0..n { if i + 1 < n && s[i] == '?' && s[i + 1] == '?' { dp[i + 1] -= 1; } if i + 2 < n && s[i] == '?' && s[i + 2] == '?' { dp[i + 2] -= 1; } } let mut ans = ModInt::new(1); for i in 0..n { ans *= dp[i]; } io.println(ans); } pub mod basic { pub const U_INF: u64 = (1 << 60) + (1 << 30); pub const I_INF: i64 = (1 << 60) + (1 << 30); pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: std::io::BufWriter>, } impl Default for IO { fn default() -> Self { Self::new() } } impl IO { pub fn new() -> Self { use std::io::*; let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } pub fn next_str(&mut self) -> &str { self.iter.next().unwrap() } pub fn read(&mut self) -> T where ::Err: std::fmt::Debug, { self.iter.next().unwrap().parse().unwrap() } pub fn next_usize(&mut self) -> usize { self.read() } pub fn next_uint(&mut self) -> u64 { self.read() } pub fn next_int(&mut self) -> i64 { self.read() } pub fn next_float(&mut self) -> f64 { self.read() } pub fn next_chars(&mut self) -> std::str::Chars { self.next_str().chars() } pub fn next_vec(&mut self, n: usize) -> Vec where ::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect::>() } pub fn print(&mut self, t: T) { use std::io::Write; write!(self.buf, "{}", t).unwrap(); } pub fn println(&mut self, t: T) { self.print(t); self.print("\n"); } pub fn print_iter>( &mut self, mut iter: I, sep: &str, ) { if let Some(v) = iter.next() { self.print(v); for vi in iter { self.print(sep); self.print(vi); } } self.print("\n"); } pub fn flush(&mut self) { use std::io::Write; self.buf.flush().unwrap(); } } }