macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } fn search(x: i64) -> i64 { if x == 0 { return 0; } for i in 0..100 { if (x & (1 << i)) != 0 { return 1+ search(x ^ (1 << i) ^ (1 << (i + 1))); } } panic!(); } fn modpow(x: i64, p: i64, m: i64) -> i64 { if p == 0 { 1 } else if p == 1 { x } else if p % 2 == 1 { x * modpow(x, p - 1, m) % m } else { let t = modpow(x, p / 2, m); t * t % m } } fn modinv(x: i64, m: i64) -> i64{ modpow(x, m - 2, m) } fn main() { let m = 998244353; input! { n: i64, k: i64, }; if false { let mut cnt = vec![0; 10]; for b in 0..(1 << n) { let x: i64 = b; if x.count_ones() % 2 == 0 { let r = search(x); println!("{:b} {} {}", x, x.count_ones(), r); cnt[r as usize] += 1; } } //dbg!(&cnt); } let mut fact = vec![1; (n + 1) as usize]; for i in 1.. (n + 1) { fact[i as usize] = fact[(i - 1) as usize] * (i as i64) % m; } let mut finv: Vec<_> = fact.iter().map(|x| modinv(*x, m)).collect(); // dbg!(&fact); // dbg!(&finv); // // for i in 0 ..(n + 1) { // fact[i as usize] = modpow(fact[i as usize], k, m); // finv[i as usize] = modpow(finv[i as usize], k, m); // dbg!(&fact[i as usize] * finv[i as usize] % m); // } let mut s = 0; for i in 0..n { let t = fact[(n - 1) as usize] % m * finv[i as usize] % m * finv[(n - i - 1) as usize] % m; //dbg!(&t); s += modpow(i, k, m) * t; s %= m; } println!("{}", s); }