#![allow(non_snake_case, unused_imports)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; } let N = input!(usize); const MOD: usize = 998_244_353; let M = 100_001; let mut U = vec![0; M]; let mut F = vec![0; M]; let mut W = vec![0; M]; let mut P = vec![0; M]; let mut all_door = 0; for _ in 0..N { let S = input!(String); let A = input!(usize); all_door += A; if S == "U" { U[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A); U[A] %= MOD; } else if S == "F" { F[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A); F[A] %= MOD; } else if S == "W" { W[A] += MOD + ntt::pow_mod(N - 1, A) - ntt::pow_mod(N - 2, A); W[A] %= MOD; } else { P[A] += ntt::pow_mod(N - 1, A); P[A] %= MOD; } } let cnt = { let a = ntt::conv(U, F); let b = ntt::conv(a, W); let c = ntt::conv(b, P); c }; let mut ans = 0; for (i, &c) in cnt.iter().enumerate() { if c > 0 { let other_pattern = ntt::pow_mod(N - 1, all_door - i); ans += c * other_pattern; ans %= MOD; } } writeln!(out, "{}", ans); } struct Scanner { reader: R, buf_str: Vec, buf_iter: str::SplitWhitespace<'static>, } impl Scanner { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } } pub mod ntt { const MOD: usize = 998_244_353; const ROOT: [usize; 24] = [ 1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, ]; const ROOT_INV: [usize; 24] = [ 1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, ]; pub fn pow_mod(x: usize, m: usize) -> usize { let mut ret = 1; let mut val = x; for i in 0..60 { if (m >> i) & 1 == 1 { ret *= val; ret %= MOD; } val *= val; val %= MOD; } ret } pub fn inv_mod(x: usize) -> usize { return pow_mod(x, MOD - 2); } pub fn ntt(mut f: Vec, depth: usize) -> Vec { let n = f.len(); if n == 1 { return f; } let mut even = vec![0; n / 2]; let mut odd = vec![0; n / 2]; for i in 0..n / 2 { even[i] = f[2 * i]; odd[i] = f[2 * i + 1]; } even = ntt(even, depth - 1); odd = ntt(odd, depth - 1); let r = ROOT[depth]; let mut now = 1; for i in 0..n / 2 { odd[i] *= now; odd[i] %= MOD; f[i] = (even[i] + odd[i]) % MOD; f[i + n / 2] = (MOD + even[i] - odd[i]) % MOD; now *= r; now %= MOD; } return f; } pub fn intt(mut f: Vec, depth: usize) -> Vec { let n = f.len(); if n == 1 { return f; } let mut even = vec![0; n / 2]; let mut odd = vec![0; n / 2]; for i in 0..n / 2 { even[i] = f[2 * i]; odd[i] = f[2 * i + 1]; } even = intt(even, depth - 1); odd = intt(odd, depth - 1); let r = ROOT_INV[depth]; let mut now = 1; for i in 0..n / 2 { odd[i] *= now; odd[i] %= MOD; f[i] = (even[i] + odd[i]) % MOD; f[i + n / 2] = (MOD + even[i] - odd[i]) % MOD; now *= r; now %= MOD; } return f; } pub fn conv(mut f: Vec, mut g: Vec) -> Vec { let mut l = 1; let mut d = 0; while f.len() + g.len() - 1 >= l { l <<= 1; d += 1; } while f.len() < l { f.push(0); } while g.len() < l { g.push(0); } assert!(f.len() == g.len()); let F = ntt(f, d); let G = ntt(g, d); assert!(F.len() == G.len()); let H = { let mut ret = vec![0; l]; for i in 0..l { ret[i] = F[i] * G[i]; ret[i] %= MOD; } ret }; let h = { let mut ret = intt(H, d); let l_inv = inv_mod(l); for i in 0..l { ret[i] *= l_inv; ret[i] %= MOD; } ret }; h } }