pub mod modint {
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
type Int = u128;
pub struct Factorial {
fact: Vec<ModInt>,
ifact: Vec<ModInt>,
}
impl Factorial {
pub fn new(n: usize) -> Self {
Self::build(n)
}
fn build(n: usize) -> Self {
let mut fact = vec![ModInt::new(1); n + 1];
let mut ifact = vec![ModInt(0); n + 1];
for i in 0..n {
fact[i + 1] = fact[i] * (i as Int + 1);
}
ifact[n] = fact[n].inv();
for i in (0..n).rev() {
ifact[i] = ifact[i + 1] * (i as Int + 1);
}
Self { fact, ifact }
}
/// nCr
pub fn comb(&self, n: usize, r: usize) -> ModInt {
if r > n {
return ModInt::new(0);
}
self.fact[n] * self.ifact[r] * self.ifact[n - r]
}
/// nPr
pub fn perm(&self, n: usize, r: usize) -> ModInt {
self.comb(n, r) * self.fact[r]
}
/// 1/n
pub fn inv(&self, n: usize) -> ModInt {
assert!(n > 0);
self.ifact[n] * self.fact[n - 1]
}
}
#[derive(Clone, Copy)]
pub struct ModInt(pub Int);
impl ModInt {
const MOD: Int = 998244353;
pub fn new(x: Int) -> Self {
Self(x % Self::MOD)
}
pub fn add(&self, other: Self) -> Self {
let mut val = self.0 + other.0;
if val >= Self::MOD {
val -= Self::MOD;
}
Self(val)
}
pub fn sub(&self, other: Self) -> Self {
let val = if self.0 >= other.0 {
self.0 - other.0
} else {
Self::MOD - other.0 + self.0
};
Self(val)
}
pub fn mul(&self, other: Self) -> Self {
Self((self.0 * other.0) % Self::MOD)
}
pub fn div(&self, other: Self) -> Self {
self.mul(other.inv())
}
pub fn pow(&self, mut n: Int) -> Self {
let mut val = 1;
let mut pow = self.0;
while n > 0 {
if (n & 1) == 1 {
val = (val * pow) % Self::MOD;
}
pow = (pow * pow) % Self::MOD;
n >>= 1;
}
Self(val)
}
pub fn inv(&self) -> Self {
self.pow(Self::MOD - 2)
}
}
impl Add for ModInt {
type Output = ModInt;
fn add(self, rhs: Self) -> Self::Output {
ModInt::add(&self, rhs)
}
}
impl Sub for ModInt {
type Output = ModInt;
fn sub(self, rhs: Self) -> Self::Output {
ModInt::sub(&self, rhs)
}
}
impl Mul for ModInt {
type Output = ModInt;
fn mul(self, rhs: Self) -> Self::Output {
ModInt::mul(&self, rhs)
}
}
impl Div for ModInt {
type Output = ModInt;
fn div(self, rhs: Self) -> Self::Output {
ModInt::div(&self, rhs)
}
}
impl Add<Int> for ModInt {
type Output = ModInt;
fn add(self, rhs: Int) -> Self::Output {
ModInt::add(&self, Self::new(rhs))
}
}
impl Sub<Int> for ModInt {
type Output = ModInt;
fn sub(self, rhs: Int) -> Self::Output {
ModInt::sub(&self, Self::new(rhs))
}
}
impl Mul<Int> for ModInt {
type Output = ModInt;
fn mul(self, rhs: Int) -> Self::Output {
ModInt::mul(&self, Self::new(rhs))
}
}
impl Div<Int> for ModInt {
type Output = ModInt;
fn div(self, rhs: Int) -> Self::Output {
ModInt::div(&self, Self::new(rhs))
}
}
impl AddAssign<ModInt> for ModInt {
fn add_assign(&mut self, rhs: ModInt) {
*self = self.add(rhs);
}
}
impl SubAssign<ModInt> for ModInt {
fn sub_assign(&mut self, rhs: ModInt) {
*self = self.sub(rhs);
}
}
impl MulAssign<ModInt> for ModInt {
fn mul_assign(&mut self, rhs: ModInt) {
*self = self.mul(rhs);
}
}
impl DivAssign<ModInt> for ModInt {
fn div_assign(&mut self, rhs: ModInt) {
*self = self.div(rhs);
}
}
impl AddAssign<Int> for ModInt {
fn add_assign(&mut self, rhs: Int) {
*self = self.add(rhs);
}
}
impl SubAssign<Int> for ModInt {
fn sub_assign(&mut self, rhs: Int) {
*self = self.sub(rhs);
}
}
impl MulAssign<Int> for ModInt {
fn mul_assign(&mut self, rhs: Int) {
*self = self.mul(rhs);
}
}
impl DivAssign<Int> for ModInt {
fn div_assign(&mut self, rhs: Int) {
*self = self.div(rhs);
}
}
}