use crate::modint::Modulo; type Mint = modint::Mint; fn main() { scan!(a: i64, n: i64); println!("{}", modint::Mod998244353::modulo()); println!("{}", Mint::raw(a).pow(n)); } #[allow(dead_code)] pub mod modint { use std::marker; use std::ops; pub trait Modulo { fn modulo() -> i64; fn primitive_root() -> i64; } #[derive(Clone, marker::Copy)] pub enum Mod998244353 {} impl Modulo for Mod998244353 { fn modulo() -> i64 { 998_244_353i64 } fn primitive_root() -> i64 { 3i64 } } #[derive(Clone, marker::Copy)] pub enum Mod1000000007 {} impl Modulo for Mod1000000007 { fn modulo() -> i64 { 1_000_000_007i64 } fn primitive_root() -> i64 { unimplemented!(); } } #[derive(Clone, Copy, PartialEq, Eq)] pub struct Mint where M: Modulo { val: i64, _p: marker::PhantomData } impl Mint where M: Modulo + marker::Copy { pub fn new(val: i64) -> Self { Mint { val: (val % M::modulo() + M::modulo()) % M::modulo(), _p: marker::PhantomData } } pub fn raw(val: i64) -> Self { assert!(0 <= val && val < M::modulo()); Mint { val, _p: marker::PhantomData } } pub fn zero() -> Self { Mint { val: 0i64, _p: marker::PhantomData } } pub fn one() -> Self { Mint { val: 1i64, _p: marker::PhantomData } } pub fn modulo() -> i64 { M::modulo() } pub fn val(&self) -> i64 { self.val } pub fn pow(&self, mut exp: i64) -> Self { let (mut val, mut res) = (self.val, 1); while exp > 0 { if exp % 2 == 1 { res = (res * val) % M::modulo(); } val = (val * val) % M::modulo(); exp >>= 1; } Self { val: res, _p: marker::PhantomData } } pub fn inv(&self) -> Self { self.pow(M::modulo() - 2) } pub fn nth_root(n: i64) -> Self { assert!(n.abs() == 1 << n.abs().trailing_zeros()); assert!(M::modulo() - 1 + (M::modulo() - 1) / n >= 0); Mint::raw(M::primitive_root()).pow(M::modulo() - 1 + (M::modulo() - 1) / n) } pub fn add_raw(&self, rhs: i64) -> Self { *self + Mint::new(rhs) } pub fn sub_raw(&self, rhs: i64) -> Self { *self - Mint::new(rhs) } pub fn mul_raw(&self, rhs: i64) -> Self { *self * Mint::new(rhs) } pub fn div_raw(&self, rhs: i64) -> Self { *self / Mint::new(rhs) } } impl Default for Mint where M: Modulo + marker::Copy { fn default() -> Self { Mint::zero() } } impl std::fmt::Debug for Mint where M: Modulo + marker::Copy { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl std::fmt::Display for Mint where M: Modulo + marker::Copy { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl ops::Add for Mint where M: Modulo + marker::Copy { type Output = Self; fn add(self, rhs: Self) -> Self::Output { Self::new(self.val + rhs.val) } } impl ops::AddAssign for Mint where M: Modulo + marker::Copy { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl ops::Sub for Mint where M: Modulo + marker::Copy { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Self::new(self.val - rhs.val + M::modulo()) } } impl ops::SubAssign for Mint where M: Modulo + marker::Copy { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl ops::Mul for Mint where M: Modulo + marker::Copy { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Self::new(self.val * rhs.val) } } impl ops::MulAssign for Mint where M: Modulo + marker::Copy { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl ops::Div for Mint where M: Modulo + marker::Copy { type Output = Self; fn div(self, rhs: Self) -> Self::Output { assert!(rhs.val != 0); self * rhs.inv() } } impl ops::DivAssign for Mint where M: Modulo + marker::Copy { fn div_assign(&mut self, rhs: Self) { assert!(rhs.val != 0); *self *= rhs.inv() } } pub struct Combination where M: Modulo { fact: Vec>, ifact: Vec> } impl Combination where M: Modulo + marker::Copy { pub fn new(size: usize) -> Self { let mut fact = vec![Mint::one(); size+1]; let mut ifact = vec![Mint::one(); size+1]; let mut buf = vec![Mint::one(); size+1]; fact.iter_mut().enumerate().skip(1).for_each(|(i, v)| { *v = buf[i-1] * Mint::raw(i as i64); buf[i] = *v; }); ifact[size] = fact[size].inv(); buf[size] = ifact[size]; ifact.iter_mut().enumerate().skip(1).rev().skip(1).for_each(|(i, v)| { *v = buf[i+1] * Mint::raw(i as i64 + 1); buf[i] = *v; }); Self { fact, ifact } } pub fn get(&self, n: usize, k: usize) -> Mint { if n < k { Mint::zero() } else { self.fact[n] * self.ifact[k] * self.ifact[n-k] } } } } mod iolib { use std::cell::RefCell; use std::io::{ Read, BufRead, Error }; use std::str::SplitWhitespace; use std::thread_local; thread_local! { static BUF_SPLIT_WHITESPACE: RefCell> = RefCell::new("".split_whitespace()); } #[inline] fn refill_buffer(interactive: bool) -> Result<(), Error> { let mut s = String::new(); if cfg!(debug_assertions) || interactive { std::io::stdin().lock().read_line(&mut s)?; } else { std::io::stdin().lock().read_to_string(&mut s)?; } BUF_SPLIT_WHITESPACE.with(|buf_str| { *buf_str.borrow_mut() = Box::leak(s.into_boxed_str()).split_whitespace(); Ok(()) }) } #[inline] pub fn scan_string(interactive: bool) -> &'static str { BUF_SPLIT_WHITESPACE.with(|buf_str| { if let Some(s) = buf_str.borrow_mut().next() { return s; } refill_buffer(interactive).unwrap(); if let Some(s) = buf_str.borrow_mut().next() { return s; } unreachable!("Read Error: No input items."); }) } #[macro_export] macro_rules! scan { // Terminator ( @interactive : $interactive:literal ) => {}; // Terminator ( @interactive : $interactive:literal, ) => {}; // Vec> ( @interactive : $interactive:literal, $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ]) => { let $v = { let len = $len; (0..len).fold(vec![], |mut v, _| { $crate::scan!(@interactive: $interactive, w: [ $( $inner )+ ]); v.push(w); v }) }; }; // Vec>, ...... ( @interactive : $interactive:literal, $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ] , $( $rest:tt )* ) => { $crate::scan!(@interactive: $interactive, [ [ $( $inner )+ ] ; $len ]); $crate::scan!(@interactive: $interactive, $( $rest )*); }; // Vec<$t> ( @interactive : $interactive:literal, $v:ident : [ $t:tt ; $len:expr ]) => { let $v = { let len = $len; (0..len).map(|_| { $crate::scan!(@interactive: $interactive, $v : $t); $v }).collect::>() }; }; // Vec<$t>, ..... ( @interactive : $interactive:literal, $v:ident : [ $t:tt ; $len:expr ] , $( $rest:tt )* ) => { let $v = { let len = $len; (0..len).map(|_| { $crate::scan!(@interactive: $interactive, $v : $t); $v }).collect::>() }; $crate::scan!(@interactive: $interactive, $( $rest )*); }; // Expand tuple ( @interactive : $interactive:literal, @expandtuple, ( $t:tt )) => { { let tmp = $crate::iolib::scan_string($interactive).parse::<$t>().unwrap(); tmp } }; // Expand tuple ( @interactive : $interactive:literal, @expandtuple, ( $t:tt $( , $rest:tt )* ) ) => { ( $crate::scan!(@interactive: $interactive, @expandtuple, ( $t )), $( $crate::scan!(@interactive: $interactive, @expandtuple, ( $rest )), )* ) }; // let $v: ($t, $u, ....) = (.......) ( @interactive : $interactive:literal, $v:ident : ( $( $rest:tt )* ) ) => { let $v = $crate::scan!(@interactive: $interactive, @expandtuple, ( $( $rest )* )); }; // let $v: $t = ...... ( @interactive : $interactive:literal, $v:ident : $t:ty ) => { let $v = $crate::iolib::scan_string($interactive).parse::<$t>().unwrap(); }; // let $v: $t = ......, ....... ( @interactive : $interactive:literal, $v:ident : $t:ty, $( $rest:tt )+ ) => { $crate::scan!(@interactive: $interactive, $v : $t); $crate::scan!(@interactive: $interactive, $( $rest )+); }; // ...... ( $( $rest:tt )* ) => { $crate::scan!(@interactive: false, $( $rest )*); }; } #[macro_export] macro_rules! scani { ( $( $rest:tt )* ) => { $crate::scan!(@interactive: true, $( $rest )*); }; } }