結果

問題 No.3394 Big Binom
コンテスト
ユーザー 👑 Mizar
提出日時 2025-12-01 00:55:40
言語 Rust
(1.83.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 19,463 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,055 ms
コンパイル使用メモリ 404,304 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-14 19:59:17
合計ジャッジ時間 25,154 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// -*- coding:utf-8-unix -*-

pub use __cargo_equip::prelude::*;

pub fn solve() -> std::io::Result<()> {
    let mut bw = FBufWriter::new(std::io::stdout().lock());

    input! {
        n: u32, mut k: u32,
    }
    if n - k < k {
        k = n - k;
    }
    use modint32static::ModIntStatic998244353 as MInt;
    let mut acc = MInt::new(1);
    let mut iacc = MInt::new(1);
    if k == 0 {
        bw.bytes_ln(b"1")?;
        return Ok(());
    }
    if ((n - k + 1)..=n).contains(&998244353) {
        bw.bytes_ln(b"0")?;
        return Ok(());
    }
    for (i, j) in ((n - k + 1)..=n).zip(1..=k) {
        acc *= MInt::new(i);
        iacc *= MInt::new(j);
    }
    bw.u_ln((acc / iacc).val())?;

    bw.flush()?;
    Ok(())
}

#[allow(unused)]
use std::{cmp::*, collections::*, hash::BuildHasherDefault};

fn main() -> std::io::Result<()> {
    const USE_THREAD: bool = false;
    if USE_THREAD {
        // In order to avoid potential stack overflow, spawn a new thread.
        let stack_size = 134_217_728; // 128 MB
        let thd = std::thread::Builder::new().stack_size(stack_size);
        thd.spawn(|| solve()).unwrap().join().unwrap()
    } else {
        solve()
    }
}

#[allow(unused)]
use {ichange::*, ifastout::*, iinput_lite::*, iinvariant::*};
#[rustfmt::skip]#[allow(unused)]mod ichange{pub use crate::__cargo_equip::prelude::*;

pub trait Change{fn chmax(&mut self,x:Self)->bool;fn chmin(&mut self,x:Self)->bool;}impl<T:PartialOrd>Change for T{fn chmax(&mut self,x:T)->bool{if*self<x{*self=x;true}else{false}}fn chmin(&mut self,x:T)->bool{if*self>x{*self=x;true}else{false}}}}
#[rustfmt::skip]#[allow(unused)]mod iinvariant{pub use crate::__cargo_equip::prelude::*;

#[macro_export]macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}}
#[rustfmt::skip]#[allow(unused)]mod iinput_lite{pub use crate::__cargo_equip::prelude::*;

#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).ok().map(|s|s.chars().collect::<Vec<_>>()))};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,Usize1)=>{read_value!($b,usize)-1};($b:expr,Isize1)=>{read_value!($b,isize)-1};($b:expr,$t:ty)=>{token($b,|s|{std::str::from_utf8(s).unwrap().parse::<$t>().unwrap()})};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($b,$t);input_inner!{$b$($r)*}};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&c|!c.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&c|c.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}let mut t=b.to_vec();r.consume(l+t.len());while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&c|c.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}
#[rustfmt::skip]#[allow(unused)]mod ifastout{pub use crate::__cargo_equip::prelude::*;

use std::*;pub use io::Write;use ptr::copy_nonoverlapping as c;type R=io::Result<()>;type P=*mut u8;const O4:u64=10000;const O8:u64=O4*O4;const O16:u64=O8*O8;const H32:u128=10u128.pow(32);macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){unsafe{hint::unreachable_unchecked()}}};}const LP:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=0x30303030|a|(b<<8)|(c<<16)|(d<<24);i+=1;}x};const LS:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=match i{0..=9=>0x30|d,10..=99=>0x3030|c|(d<<8),100..=999=>0x303030|b|(c<<8)|(d<<16),_=>0x30303030|a|(b<<8)|(c<<16)|(d<<24),};i+=1;}x};#[inline]unsafe fn d4(v:&mut P,x:u64){invariant!(x<O4);c(LP[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(4)}#[inline]unsafe fn d4l(v:&mut P,x:u64){invariant!(x<O4);c(LS[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(1+(x>9)as usize+(x>99)as usize+(x>999)as usize);}#[inline]unsafe fn d8(v:&mut P,x:u64){invariant!(x<O8);let(y0,y1)=drq4(x);d4(v,y0);d4(v,y1)}#[inline]unsafe fn d16(v:&mut P,x:u64){invariant!(x<O16);let(y0,y1)=dro8(x);d8(v,y0);d8(v,y1)}#[inline]unsafe fn d8l(v:&mut P,x:u64){invariant!(x<O8);if x<O4{d4l(v,x)}else{let(y0,y1)=drq4(x as _);d4l(v,y0);d4(v,y1)}}#[inline]unsafe fn d16l(v:&mut P,x:u64){invariant!(x<O16);if x<O8{d8l(v,x)}else{let(y0,y1)=dro8(x);d8l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du8(v:&mut P,x:u8){d4l(v,x as _)}#[inline]pub unsafe fn du16(v:&mut P,x:u16){d8l(v,x as _)}#[inline]pub unsafe fn du32(v:&mut P,x:u32){if x<O8 as _{d8l(v,x as _)}else{let(y0,y1)=drq8(x as _);invariant!(y0<43);d4l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du64(v:&mut P,x:u64){if x<O16{d16l(v,x)}else{let(y0,y1)=dro16(x);invariant!(y0<1845);d4l(v,y0);d16(v,y1)}}#[inline]pub unsafe fn dusize(v:&mut P,x:usize){du64(v,u64::try_from(x).unwrap())}#[inline]fn drh_16(x:u128)->(u64,u64){invariant!(x<0xd8e03efa8ff0175cfffffffff0000);let q=((((x>>52)as u64)as u128*8307674973655724205)>>64)as u64;let r=(x as u64).wrapping_sub(q.wrapping_mul(O16));if let Some(s)=r.checked_sub(O16){(q+1,s)}else{(q,r)}}const O19:u64=1000*O16;const H19:u128=O19 as _;#[inline]unsafe fn d3(v:&mut P,x:u64){invariant!(x<1000);c((LP[x as usize]>>8).to_le_bytes().as_ptr(),*v,4);*v=v.add(3);}#[inline]unsafe fn d19(v:&mut P,x:u64){invariant!(x<O19);let(y0,y1)=dro16(x);d3(v,y0);d16(v,y1);}#[inline]fn drh19(x:u128)->(u64,u64){invariant!(x>>64<H19);let q=((x>>64)*17014118346046923173>>64)as u64;let r=((x>>19)as u64).wrapping_sub(q.wrapping_mul(O19>>18));let s=(r as u128*519229685853483>>93)as u64;(q*2+s,(x as u64&0x7ffff)|(r<<19).wrapping_sub(O19*s))}#[inline]fn dro16(x:u64)->(u64,u64){let q=(x as u128*4153837486827862103>>115)as u64;(q,x-q*O16)}#[inline]fn dro8(x:u64)->(u64,u64){invariant!(x<O16);let q=(x as u128*12379400392853802749>>90)as u64;(q,x-q*O8)}#[inline]fn drq8(x:u64)->(u64,u64){invariant!(x>>32==0);let q=(x as u128*184467440738>>64)as u64;(q,x-q*O8)}#[inline]fn drq4(x:u64)->(u64,u64){invariant!(x<O8);let q=(x as u128*1844674407370956>>64)as u64;(q,x-q*O4)}#[inline]pub unsafe fn du128(v:&mut P,x:u128){if x<=u64::MAX as u128{du64(v,x as u64)}else if(x>>64)<H19{let(y0,y1)=drh19(x);du64(v,y0);d19(v,y1);}else{let mut y0=(((x>>64)*3402823)>>64)as u64;let mut y1=x-y0 as u128*H32;if let Some(yt)=y1.checked_sub(H32){y1=yt;y0+=1;}invariant!(702<y0&&y0<3402824);d8l(v,y0);let(z0,z1)=drh_16(y1);d16(v,z0);d16(v,z1)}}#[inline]unsafe fn dmn(v:&mut*mut u8){**v=b'-';*v=(*v).add(1)}macro_rules!imi{($i:ident,$u:ident,$t:ty)=>{#[inline]pub unsafe fn$i(v:&mut P,x:$t){if x<0{dmn(v);}$u(v,x.unsigned_abs());}};}imi!(di8,du8,i8);imi!(di16,du16,i16);imi!(di32,du32,i32);imi!(di64,du64,i64);imi!(disize,dusize,isize);imi!(di128,du128,i128);macro_rules!imf{($f:ident,$spf:ident,$fsp:ident,$fln:ident,$fv:ident,$ty:ty,$d:ident)=>{#[inline]pub fn$f<U:Into<$ty>>(&mut self,x:U)->R{unsafe{$d(&mut self.p,x.into());}if self.p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$spf<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{*p=b' ';p=p.add(1);$d(&mut p,x.into());}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fsp<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b' ';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fln<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b'\n';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}pub fn$fv<U:Copy+Into<$ty>>(&mut self,x:&[U])->R{if!x.is_empty(){self.$f(x[0])?;for&y in x[1..].iter(){self.$spf(y)?;}}unsafe{*self.p=b'\n';self.p=self.p.add(1);}if self.p>=self.limit{self.flush()?}Ok(())}};}const SBUF:usize=65536;const SLIM:usize=SBUF-48;pub struct FBufWriter<W:Write>{inner:Option<W>,buf:Box<[mem::MaybeUninit<u8>;SBUF]>,limit:*mut u8,p:*mut u8,}impl<W:Write>Write for FBufWriter<W>{fn write(&mut self,b:&[u8])->io::Result<usize>{let bl=b.len();let space=unsafe{self.limit.offset_from(self.p)as usize};if bl<=SBUF-SLIM{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl);}if self.p>self.limit{self.flush()?}}else if SLIM<bl{self.flush()?;self.inner.as_mut().unwrap().write_all(b)?}else if space<bl{unsafe{c(b.as_ptr(),self.p,space);self.p=self.limit;}self.flush()?;let b=&b[space..];unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len())}}else{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl)}}Ok(bl)}fn flush(&mut self)->io::Result<()>{let base=self.buf.as_mut_ptr()as*mut u8;if self.p>base{unsafe{let len=self.p.offset_from(base)as usize;self.inner.as_mut().unwrap().write_all(slice::from_raw_parts(base,len))?;self.p=base;}}Ok(())}}impl<W:Write>Drop for FBufWriter<W>{fn drop(&mut self){let _=self.flush();}}impl<W:Write>FBufWriter<W>{pub fn new(inner:W)->Self{let mut buf=Box::new([mem::MaybeUninit::uninit();SBUF]);unsafe{let base=buf.as_mut_ptr()as*mut u8;FBufWriter{inner:Some(inner),buf,limit:base.add(SLIM),p:base,}}}pub fn into_inner(mut self)->W{self.flush().unwrap();self.inner.take().unwrap()}imf!(u8,sp_u8,u8_sp,u8_ln,u8v,u8,du8);imf!(u16,sp_u16,u16_sp,u16_ln,u16v,u16,du16);imf!(u32,sp_u32,u32_sp,u32_ln,u32v,u32,du32);imf!(u64,sp_u64,u64_sp,u64_ln,u64v,u64,du64);imf!(usize,sp_usize,usize_sp,usize_ln,usizev,usize,dusize);imf!(u128,sp_u128,u128_sp,u128_ln,u128v,u128,du128);imf!(u,sp_u,u_sp,u_ln,uv,u128,du128);imf!(i8,sp_i8,i8_sp,i8_ln,i8v,i8,di8);imf!(i16,sp_i16,i16_sp,i16_ln,i16v,i16,di16);imf!(i32,sp_i32,i32_sp,i32_ln,i32v,i32,di32);imf!(i64,sp_i64,i64_sp,i64_ln,i64v,i64,di64);imf!(isize,sp_isize,isize_sp,isize_ln,isizev,isize,disize);imf!(i128,sp_i128,i128_sp,i128_ln,i128v,i128,di128);imf!(i,sp_i,i_sp,i_ln,iv,i128,di128);#[inline]pub fn byte(&mut self,b:u8)->R{unsafe{*self.p=b;self.p=self.p.add(1);}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]fn sbytes(&mut self,b:&[u8])->R{invariant!(b.len()<=SBUF-SLIM);unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len());}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]pub fn bytes(&mut self,b:&[u8])->R{self.write(b).map(|_|())}pub fn bytes_ln(&mut self,b:&[u8])->R{self.bytes(b)?;self.ln()}#[inline]pub fn str(&mut self,s:&str)->R{self.bytes(s.as_bytes())}#[inline]pub fn sp(&mut self)->R{self.byte(b' ')}#[inline]pub fn ln(&mut self)->R{self.byte(b'\n')}#[inline]pub fn yes(&mut self,x:bool)->R{if x{self.sbytes(b"Yes")}else{self.sbytes(b"No")}}#[inline]pub fn yes_ln(&mut self,x:bool)->R{if x{self.sbytes(b"Yes\n")}else{self.sbytes(b"No\n")}}}}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=096a436#mizar-competitive-integer-modint32static@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint32static`
///  - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=096a436#mizar-competitive-misc-invariant@0.0.0`         licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__mizar_competitive_misc_invariant_0_0_0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod modint32static {use crate::__cargo_equip::preludes::modint32static::*;pub use crate::__cargo_equip::macros::modint32static::*;pub trait ModInt32Static{const MOD:u32;const TZ:u32;const MX:u32;const IMX:u32;const MYM:u32;const IBIN:[u32;64];fn norm_impl(n:u32)->u32;fn add_impl(lhs:u32,rhs:u32)->u32;fn sub_impl(lhs:u32,rhs:u32)->u32;fn mul_impl(lhs:u32,rhs:u32)->u32;fn mul_mx(lhs:u32,rhs:u32)->u32;fn pow_impl(lhs:u32,rhs:u32)->u32;fn div_impl(lhs:u32,rhs:u32)->Option<u32>;fn inv_plain(n:u32)->Option<u32>;fn inv_mx(n:u32)->Option<u32>;fn inv_my(n:u32)->Option<u32>;fn inv_impl(n:u32)->Option<u32>;}#[macro_export]macro_rules!__cargo_equip_macro_def_modint32static_modint32static_impl{($modulus:literal,$st:ident)=>{modint32static_impl!(@dol($)$modulus,$st);};(@dol($dol:tt)$modulus:literal,$st:ident)=>{#[derive(Copy,Clone)]pub struct$st(u32);impl ModInt32Static for$st{const MOD:u32=($modulus as u32);const TZ:u32=($modulus as u32).trailing_zeros();const MX:u32=(Self::MOD>>(Self::TZ&31))|((Self::MOD==0)as u32);const IMX:u32={let mx=Self::MX;let mut x=mx;x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x};const MYM:u32=((Self::TZ!=0)as u32).wrapping_neg()>>((32-Self::TZ)&31);const IBIN:[u32;64]={let mut ibin=[0u32;64];ibin[0]=1;const fn div2(x:u32,m:u32)->u32{x/2+((x&1).wrapping_neg()&(m/2+1))}macro_rules!div2{($dol($dol i:literal),*)=>{$dol(ibin[$dol i+1]=div2(ibin[$dol i],Self::MX);)*};}div2!(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62);ibin};#[inline]fn norm_impl(x:u32)->u32{if Self::MOD==0{x}else{x%Self::MOD}}#[inline]fn add_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_add(rhs);}let v=u64::from(lhs)+u64::from(rhs);match v.checked_sub(u64::from(Self::MOD)){None=>v as u32,Some(w)=>w as u32,}}#[inline]fn sub_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_sub(rhs);}let(v,f)=lhs.overflowing_sub(rhs);v.wrapping_add(u32::from(f).wrapping_neg()&Self::MOD)}#[inline]fn mul_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_mul(rhs);}(u64::from(lhs)*u64::from(rhs)%u64::from(Self::MOD))as u32}#[inline]fn mul_mx(lhs:u32,rhs:u32)->u32{(u64::from(lhs)*u64::from(rhs)%u64::from(Self::MX))as u32}#[inline]fn pow_impl(lhs:u32,mut rhs:u32)->u32{if rhs==0{return u32::from(Self::MOD!=1);}let mut t=lhs;while rhs%2==0{t=Self::mul_impl(t,t);rhs/=2;}let mut r=t;rhs/=2;while rhs!=0{t=Self::mul_impl(t,t);if rhs%2!=0{r=Self::mul_impl(r,t);}rhs/=2;}r}#[inline]fn div_impl(lhs:u32,rhs:u32)->Option<u32>{Self::inv_impl(rhs).map(|irhs|Self::mul_impl(lhs,irhs))}#[inline]fn inv_plain(n:u32)->Option<u32>{let m=Self::MOD;let(mut a,mut b,mut x,mut y)=(1,0,n,m);loop{match x{0=>break None,1=>break Some(a),_=>{}}b+=a*(y/x);y%=x;match y{0=>break None,1=>break Some(m-b),_=>{}}a+=b*(x/y);x%=y;}}#[inline]fn inv_mx(n:u32)->Option<u32>{if Self::MX%2==0{unsafe{core::hint::unreachable_unchecked()}}if Self::MX==1{return Some(0);}let(mut a,mut b,mut x,mut y)=(1,0,n,Self::MX);if x==0{return None;}let mut s=n.trailing_zeros();x>>=s;loop{if x==1{return Some(Self::mul_mx(a,Self::IBIN[s as usize]));}if x==y{return None;}if x<=(y>>3){if x==0{unsafe{core::hint::unreachable_unchecked()}}let(q,r)=(y/x,y%x);b+=a*q;y=r;if y==0{return None;}let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}else{while y>x{y-=x;b+=a;let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}}if y==1{return Some(Self::mul_mx(Self::MX-b,Self::IBIN[s as usize]));}if(x>>3)>=y{if y==0{unsafe{core::hint::unreachable_unchecked()}}let(q,r)=(x/y,x%y);a+=b*q;x=r;if x==0{return None;}let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}else{while x>y{x-=y;a+=b;let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}}}}#[inline]fn inv_my(n:u32)->Option<u32>{if Self::TZ==0{return Some(0);}if n%2==0{return None;}Some(Self::MYM&match Self::TZ{21..=0xffff_ffff=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}11..=20=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}6..=10=>{let t=n.wrapping_mul(3)^2;t.wrapping_mul(2u32.wrapping_sub(n.wrapping_mul(t)))}4..=5=>n.wrapping_mul(3)^2,0..=3=>n,})}#[inline]fn inv_impl(n:u32)->Option<u32>{if Self::TZ==0{return Self::inv_mx(n);}if Self::MX==1{return Self::inv_my(n);}if let Some(y)=Self::inv_my(n){if let Some(x)=Self::inv_mx(n){let(t,f)=x.overflowing_sub(Self::MX*(Self::IMX.wrapping_mul(x.wrapping_sub(y))&Self::MYM));return Some(t.wrapping_add((f as u32).wrapping_neg()&Self::MOD));}}return None;}}impl std::ops::Add for$st{type Output=Self;#[inline]fn add(self,rhs:Self)->Self::Output{$st($st::add_impl(self.0,rhs.0))}}impl std::ops::Sub for$st{type Output=Self;#[inline]fn sub(self,rhs:Self)->Self::Output{$st($st::sub_impl(self.0,rhs.0))}}impl std::ops::Mul for$st{type Output=Self;#[inline]fn mul(self,rhs:Self)->Self::Output{$st($st::mul_impl(self.0,rhs.0))}}impl std::ops::Div for$st{type Output=Self;#[inline]fn div(self,rhs:Self)->Self::Output{$st($st::div_impl(self.0,rhs.0).unwrap())}}impl std::ops::Neg for$st{type Output=Self;#[inline]fn neg(self)->Self::Output{$st($st::sub_impl(0,self.0))}}impl std::ops::AddAssign for$st{#[inline]fn add_assign(&mut self,rhs:Self){*self=Self(Self::add_impl(self.0,rhs.0));}}impl std::ops::SubAssign for$st{#[inline]fn sub_assign(&mut self,rhs:Self){*self=Self(Self::sub_impl(self.0,rhs.0));}}impl std::ops::MulAssign for$st{#[inline]fn mul_assign(&mut self,rhs:Self){*self=Self(Self::mul_impl(self.0,rhs.0));}}impl std::ops::DivAssign for$st{#[inline]fn div_assign(&mut self,rhs:Self){*self=Self(Self::div_impl(self.0,rhs.0).unwrap());}}impl$st{#[inline]pub fn new(n:u32)->Self{Self(Self::norm_impl(n))}#[inline]pub fn raw(n:u32)->Self{debug_assert!(n<Self::MOD||Self::MOD==0);Self(n)}#[inline]pub fn val(&self)->u32{self.0}#[inline]pub fn pow(&self,r:u32)->Self{Self(Self::pow_impl(self.0,r))}#[inline]pub fn inv(&self)->Option<Self>{Self::inv_impl(self.0).map(|ni|Self(ni))}}};}macro_rules!modint32static_impl{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_modint32static_modint32static_impl!{$($tt)*})}modint32static_impl!(998244353,ModIntStatic998244353);modint32static_impl!(1000000007,ModIntStatic1000000007);}
        pub mod __mizar_competitive_misc_invariant_0_0_0 {pub use crate::__cargo_equip::macros::__mizar_competitive_misc_invariant_0_0_0::*;#[macro_export]macro_rules!__cargo_equip_macro_def___mizar_competitive_misc_invariant_0_0_0_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___mizar_competitive_misc_invariant_0_0_0_invariant!{$($tt)*})}}
    }

    pub(crate) mod macros {
        pub mod modint32static {pub use crate::__cargo_equip_macro_def_modint32static_modint32static_impl as modint32static_impl;}
        pub mod __mizar_competitive_misc_invariant_0_0_0 {pub use crate::__cargo_equip_macro_def___mizar_competitive_misc_invariant_0_0_0_invariant as invariant;}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod modint32static {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__mizar_competitive_misc_invariant_0_0_0 as invariant;}
        pub mod __mizar_competitive_misc_invariant_0_0_0 {}
    }
}
0