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 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) } const K: i64 = 40; const M: i64 = 998244353; struct Solver { n: i64, m: i64, fact: Vec, finv: Vec, } impl Solver { fn new(n: i64, m: i64) -> Self { let mut fact = vec![1; (K + 1) as usize]; for i in 1..(K + 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(); return Solver { n, m, fact, finv } } fn choose(&self, n: i64, m: i64) -> i64 { self.fact[n as usize] * self.finv[m as usize] % M * self.finv[(n - m) as usize] % M } fn countit(&self, popcount: i64) -> i64 { modpow(self.n, popcount, M) } fn search(&self, a: i64, k: i64) -> i64 { if k == -1 { // a自身のぶん。どこでも0にしなかったやつ。 return self.countit(a.count_ones().into()); } let mut ans = 0; if (a & (1_i64 << k)) != 0 { // kより上はa通り、k番目は0、kより下は2^k // i bits are one (lower k bits) for i in 0..(k + 1) { let t = self.choose(k, i); let f = (a >> (k + 1)).count_ones() as i64 + i; // dbg!((k, i, t, f)); ans += self.countit(f) * t % M; ans %= M; } } ans += self.search(a, k - 1); ans %= M; return ans } fn solve(&mut self) { println!("{}", self.search(self.m, 35)); } } fn main() { input! { n: i64, m: i64, }; let mut solver = Solver::new(n, m); // dbg!(&solver.countit(0)); // dbg!(&solver.countit(1)); // dbg!(&solver.countit(2)); solver.solve(); }