Submission #70663129

---

Source Code Expand

pub use __cargo_equip::prelude::*;

use acl_modint::ModInt998244353 as Mint;
use proconio::input;
use proth_fps::FormalPowerSeries as Fps;
type Fps9 = Fps<Mint>;

fn main() {
    input! {
        n: usize,
    };
    let f = Fps9::from_vec(vec![Mint::new(0), Mint::new(-1), Mint::new(-2).inv()]);
    let mut f = f.exp_until(n + 1);
    for i in 0..n {
        let e = f[i];
        f[i + 1] += e;
    }
    f.fact_mul();
    println!("{}", f[n]);
}

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

///  # Bundled libraries
/// 
///  - `ac-library-rs-parted-internal-bit 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`                           licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0`
///  - `ac-library-rs-parted-internal-math 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`                          licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0`
///  - `ac-library-rs-parted-modint 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)`                                 licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_modint`
///  - `acl-convolution-unwrap 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████████████████)`          published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__acl_convolution_unwrap_0_1_0`
///  - `proth-fps 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)`                                   published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::proth_fps`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {pub use self::internal_bit::*;mod internal_bit{#[allow(dead_code)]pub fn ceil_pow2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}}
        pub mod __ac_library_rs_parted_internal_math_0_1_0 {pub use self::internal_math::*;mod internal_math{#![allow(dead_code)]use std::mem::swap;pub fn safe_mod(mut x:i64,m:i64)->i64{x%=m;if x<0{x+=m;}x}pub struct Barrett{pub _m:u32,pub im:u64,}impl Barrett{pub fn new(m:u32)->Barrett{Barrett{_m:m,im:(-1i64 as u64/m as u64).wrapping_add(1),}}pub fn umod(&self)->u32{self._m}#[allow(clippy::many_single_char_names)]pub fn mul(&self,a:u32,b:u32)->u32{mul_mod(a,b,self._m,self.im)}}#[allow(clippy::many_single_char_names)]pub fn mul_mod(a:u32,b:u32,m:u32,im:u64)->u32{let mut z=a as u64;z*=b as u64;let x=(((z as u128)*(im as u128))>>64)as u64;let mut v=z.wrapping_sub(x.wrapping_mul(m as u64))as u32;if m<=v{v=v.wrapping_add(m);}v}#[allow(clippy::many_single_char_names)]pub fn pow_mod(x:i64,mut n:i64,m:i32)->i64{if m==1{return 0;}let _m=m as u32;let mut r:u64=1;let mut y:u64=safe_mod(x,m as i64)as u64;while n!=0{if(n&1)>0{r=(r*y)%(_m as u64);}y=(y*y)%(_m as u64);n>>=1;}r as i64}pub fn is_prime(n:i32)->bool{let n=n as i64;match n{_ if n<=1=>return false,2|7|61=>return true,_ if n%2==0=>return false,_=>{}}let mut d=n-1;while d%2==0{d/=2;}for&a in&[2,7,61]{let mut t=d;let mut y=pow_mod(a,t,n as i32);while t!=n-1&&y!=1&&y!=n-1{y=y*y%n;t<<=1;}if y!=n-1&&t%2==0{return false;}}true}#[allow(clippy::many_single_char_names)]pub fn inv_gcd(a:i64,b:i64)->(i64,i64){let a=safe_mod(a,b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;swap(&mut s,&mut t);swap(&mut m0,&mut m1);}if m0<0{m0+=b/s;}(s,m0)}pub fn primitive_root(m:i32)->i32{match m{2=>return 1,167_772_161=>return 3,469_762_049=>return 3,754_974_721=>return 11,998_244_353=>return 3,_=>{}}let mut divs=[0;20];divs[0]=2;let mut cnt=1;let mut x=(m-1)/2;while x%2==0{x/=2;}for i in(3..std::i32::MAX).step_by(2){if i as i64*i as i64>x as i64{break;}if x%i==0{divs[cnt]=i;cnt+=1;while x%i==0{x/=i;}}}if x>1{divs[cnt]=x;cnt+=1;}let mut g=2;loop{if(0..cnt).all(|i|pow_mod(g,((m-1)/divs[i])as i64,m)!=1){break g as i32;}g+=1;}}}}
        pub mod acl_modint {use crate::__cargo_equip::preludes::acl_modint::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0 as internal_math;pub use self::modint::*;mod modint{use crate::__cargo_equip::preludes::acl_modint::*;use super::internal_math;use std::{cell::RefCell,convert::{Infallible,TryInto as _},fmt,hash::{Hash,Hasher},iter::{Product,Sum},marker::PhantomData,ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},str::FromStr,sync::atomic::{self,AtomicU32,AtomicU64},thread::LocalKey,};pub type ModInt1000000007=StaticModInt<Mod1000000007>;pub type ModInt998244353=StaticModInt<Mod998244353>;pub type ModInt=DynamicModInt<DefaultId>;#[derive(Copy,Clone,Eq,PartialEq)]#[repr(transparent)]pub struct StaticModInt<M>{val:u32,phantom:PhantomData<fn()->M>,}impl<M:Modulus>StaticModInt<M>{#[inline(always)]pub fn modulus()->u32{M::VALUE}#[inline]pub fn new<T:RemEuclidU32>(val:T)->Self{Self::raw(val.rem_euclid_u32(M::VALUE))}#[inline]pub fn raw(val:u32)->Self{Self{val,phantom:PhantomData,}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn pow(self,n:u64)->Self{<Self as ModIntBase>::pow(self,n)}#[inline]pub fn inv(self)->Self{if M::HINT_VALUE_IS_PRIME{if self.val()==0{panic!("attempt to divide by zero");}debug_assert!(internal_math::is_prime(M::VALUE.try_into().unwrap()),"{} is not a prime number",M::VALUE,);self.pow((M::VALUE-2).into())}else{Self::inv_for_non_prime_modulus(self)}}}impl<M:Modulus>ModIntBase for StaticModInt<M>{#[inline(always)]fn modulus()->u32{Self::modulus()}#[inline]fn raw(val:u32)->Self{Self::raw(val)}#[inline]fn val(self)->u32{self.val()}#[inline]fn inv(self)->Self{self.inv()}}pub trait Modulus:'static+Copy+Eq{const VALUE:u32;const HINT_VALUE_IS_PRIME:bool;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum Mod1000000007{}impl Modulus for Mod1000000007{const VALUE:u32=1_000_000_007;const HINT_VALUE_IS_PRIME:bool=true;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>{thread_local!{static BUTTERFLY_CACHE:RefCell<Option<ButterflyCache<Mod1000000007>>>=RefCell::default();}&BUTTERFLY_CACHE}}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum Mod998244353{}impl Modulus for Mod998244353{const VALUE:u32=998_244_353;const HINT_VALUE_IS_PRIME:bool=true;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>{thread_local!{static BUTTERFLY_CACHE:RefCell<Option<ButterflyCache<Mod998244353>>>=RefCell::default();}&BUTTERFLY_CACHE}}pub struct ButterflyCache<M>{pub sum_e:Vec<StaticModInt<M>>,pub sum_ie:Vec<StaticModInt<M>>,}#[derive(Copy,Clone,Eq,PartialEq)]#[repr(transparent)]pub struct DynamicModInt<I>{val:u32,phantom:PhantomData<fn()->I>,}impl<I:Id>DynamicModInt<I>{#[inline]pub fn modulus()->u32{I::companion_barrett().umod()}#[inline]pub fn set_modulus(modulus:u32){if modulus==0{panic!("the modulus must not be 0");}I::companion_barrett().update(modulus);}#[inline]pub fn new<T:RemEuclidU32>(val:T)->Self{<Self as ModIntBase>::new(val)}#[inline]pub fn raw(val:u32)->Self{Self{val,phantom:PhantomData,}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn pow(self,n:u64)->Self{<Self as ModIntBase>::pow(self,n)}#[inline]pub fn inv(self)->Self{Self::inv_for_non_prime_modulus(self)}}impl<I:Id>ModIntBase for DynamicModInt<I>{#[inline]fn modulus()->u32{Self::modulus()}#[inline]fn raw(val:u32)->Self{Self::raw(val)}#[inline]fn val(self)->u32{self.val()}#[inline]fn inv(self)->Self{self.inv()}}pub trait Id:'static+Copy+Eq{fn companion_barrett()->&'static Barrett;}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum DefaultId{}impl Id for DefaultId{fn companion_barrett()->&'static Barrett{static BARRETT:Barrett=Barrett::default();&BARRETT}}pub struct Barrett{m:AtomicU32,im:AtomicU64,}impl Barrett{#[inline]pub const fn new(m:u32)->Self{Self{m:AtomicU32::new(m),im:AtomicU64::new((-1i64 as u64/m as u64).wrapping_add(1)),}}#[inline]const fn default()->Self{Self::new(998_244_353)}#[inline]fn update(&self,m:u32){let im=(-1i64 as u64/m as u64).wrapping_add(1);self.m.store(m,atomic::Ordering::SeqCst);self.im.store(im,atomic::Ordering::SeqCst);}#[inline]fn umod(&self)->u32{self.m.load(atomic::Ordering::SeqCst)}#[inline]fn mul(&self,a:u32,b:u32)->u32{let m=self.m.load(atomic::Ordering::SeqCst);let im=self.im.load(atomic::Ordering::SeqCst);internal_math::mul_mod(a,b,m,im)}}impl Default for Barrett{#[inline]fn default()->Self{Self::default()}}pub trait ModIntBase:Default+FromStr+From<i8>+From<i16>+From<i32>+From<i64>+From<i128>+From<isize>+From<u8>+From<u16>+From<u32>+From<u64>+From<u128>+From<usize>+Copy+Eq+Hash+fmt::Display+fmt::Debug+Neg<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign{fn modulus()->u32;fn raw(val:u32)->Self;fn val(self)->u32;fn inv(self)->Self;#[inline]fn new<T:RemEuclidU32>(val:T)->Self{Self::raw(val.rem_euclid_u32(Self::modulus()))}#[inline]fn pow(self,mut n:u64)->Self{let mut x=self;let mut r=Self::raw(1);while n>0{if n&1==1{r*=x;}x*=x;n>>=1;}r}}pub trait RemEuclidU32{fn rem_euclid_u32(self,modulus:u32)->u32;}macro_rules!impl_rem_euclid_u32_for_small_signed{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self as i64).rem_euclid(i64::from(modulus))as _}})*}}impl_rem_euclid_u32_for_small_signed!(i8,i16,i32,i64,isize);impl RemEuclidU32 for i128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self.rem_euclid(i128::from(modulus))as _}}macro_rules!impl_rem_euclid_u32_for_small_unsigned{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}})*}}macro_rules!impl_rem_euclid_u32_for_large_unsigned{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%(modulus as$ty))as _}})*}}impl_rem_euclid_u32_for_small_unsigned!(u8,u16,u32);impl_rem_euclid_u32_for_large_unsigned!(u64,u128);#[cfg(target_pointer_width="32")]impl_rem_euclid_u32_for_small_unsigned!(usize);#[cfg(target_pointer_width="64")]impl_rem_euclid_u32_for_large_unsigned!(usize);trait InternalImplementations:ModIntBase{#[inline]fn inv_for_non_prime_modulus(this:Self)->Self{let(gcd,x)=internal_math::inv_gcd(this.val().into(),Self::modulus().into());if gcd!=1{panic!("the multiplicative inverse does not exist");}Self::new(x)}#[inline]fn default_impl()->Self{Self::raw(0)}#[inline]fn from_str_impl(s:&str)->Result<Self,Infallible>{Ok(s.parse::<i64>().map(Self::new).unwrap_or_else(|_|todo!("parsing as an arbitrary precision integer?")))}#[inline]fn hash_impl(this:&Self,state:&mut impl Hasher){this.val().hash(state)}#[inline]fn display_impl(this:&Self,f:&mut fmt::Formatter)->fmt::Result{fmt::Display::fmt(&this.val(),f)}#[inline]fn debug_impl(this:&Self,f:&mut fmt::Formatter)->fmt::Result{fmt::Debug::fmt(&this.val(),f)}#[inline]fn neg_impl(this:Self)->Self{Self::sub_impl(Self::raw(0),this)}#[inline]fn add_impl(lhs:Self,rhs:Self)->Self{let modulus=Self::modulus();let mut val=lhs.val()+rhs.val();if val>=modulus{val-=modulus;}Self::raw(val)}#[inline]fn sub_impl(lhs:Self,rhs:Self)->Self{let modulus=Self::modulus();let mut val=lhs.val().wrapping_sub(rhs.val());if val>=modulus{val=val.wrapping_add(modulus)}Self::raw(val)}fn mul_impl(lhs:Self,rhs:Self)->Self;#[inline]fn div_impl(lhs:Self,rhs:Self)->Self{Self::mul_impl(lhs,rhs.inv())}}impl<M:Modulus>InternalImplementations for StaticModInt<M>{#[inline]fn mul_impl(lhs:Self,rhs:Self)->Self{Self::raw((u64::from(lhs.val())*u64::from(rhs.val())%u64::from(M::VALUE))as u32)}}impl<I:Id>InternalImplementations for DynamicModInt<I>{#[inline]fn mul_impl(lhs:Self,rhs:Self)->Self{Self::raw(I::companion_barrett().mul(lhs.val,rhs.val))}}macro_rules!impl_basic_traits{()=>{};(impl<$generic_param:ident:$generic_param_bound:tt>_ for$self:ty;$($rest:tt)*)=>{impl<$generic_param:$generic_param_bound>Default for$self{#[inline]fn default()->Self{Self::default_impl()}}impl<$generic_param:$generic_param_bound>FromStr for$self{type Err=Infallible;#[inline]fn from_str(s:&str)->Result<Self,Infallible>{Self::from_str_impl(s)}}impl<$generic_param:$generic_param_bound,V:RemEuclidU32>From<V>for$self{#[inline]fn from(from:V)->Self{Self::new(from)}}#[allow(clippy::derive_hash_xor_eq)]impl<$generic_param:$generic_param_bound>Hash for$self{#[inline]fn hash<H:Hasher>(&self,state:&mut H){Self::hash_impl(self,state)}}impl<$generic_param:$generic_param_bound>fmt::Display for$self{#[inline]fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{Self::display_impl(self,f)}}impl<$generic_param:$generic_param_bound>fmt::Debug for$self{#[inline]fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{Self::debug_impl(self,f)}}impl<$generic_param:$generic_param_bound>Neg for$self{type Output=$self;#[inline]fn neg(self)->$self{Self::neg_impl(self)}}impl<$generic_param:$generic_param_bound>Neg for&'_$self{type Output=$self;#[inline]fn neg(self)->$self{<$self>::neg_impl(*self)}}impl_basic_traits!($($rest)*);};}impl_basic_traits!{impl<M:Modulus>_ for StaticModInt<M>;impl<I:Id>_ for DynamicModInt<I>;}macro_rules!impl_bin_ops{()=>{};(for<$($generic_param:ident:$generic_param_bound:tt),*><$lhs_ty:ty>~<$rhs_ty:ty>->$output:ty{{$lhs_body:expr}~{$rhs_body:expr}}$($rest:tt)*)=>{impl<$($generic_param:$generic_param_bound),*>Add<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn add(self,rhs:$rhs_ty)->$output{<$output>::add_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Sub<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn sub(self,rhs:$rhs_ty)->$output{<$output>::sub_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Mul<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn mul(self,rhs:$rhs_ty)->$output{<$output>::mul_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Div<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn div(self,rhs:$rhs_ty)->$output{<$output>::div_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl_bin_ops!($($rest)*);};}macro_rules!impl_assign_ops{()=>{};(for<$($generic_param:ident:$generic_param_bound:tt),*><$lhs_ty:ty>~=<$rhs_ty:ty>{_~={$rhs_body:expr}}$($rest:tt)*)=>{impl<$($generic_param:$generic_param_bound),*>AddAssign<$rhs_ty>for$lhs_ty{#[inline]fn add_assign(&mut self,rhs:$rhs_ty){*self=*self+apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>SubAssign<$rhs_ty>for$lhs_ty{#[inline]fn sub_assign(&mut self,rhs:$rhs_ty){*self=*self-apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>MulAssign<$rhs_ty>for$lhs_ty{#[inline]fn mul_assign(&mut self,rhs:$rhs_ty){*self=*self*apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>DivAssign<$rhs_ty>for$lhs_ty{#[inline]fn div_assign(&mut self,rhs:$rhs_ty){*self=*self/apply($rhs_body,rhs);}}impl_assign_ops!($($rest)*);};}#[inline]fn apply<F:FnOnce(X)->O,X,O>(f:F,x:X)->O{f(x)}impl_bin_ops!{for<M:Modulus><StaticModInt<M> >~<StaticModInt<M> >->StaticModInt<M>{{|x|x}~{|x|x}}for<M:Modulus><StaticModInt<M> >~<&'_ StaticModInt<M> >->StaticModInt<M>{{|x|x}~{|&x|x}}for<M:Modulus><&'_ StaticModInt<M> >~<StaticModInt<M> >->StaticModInt<M>{{|&x|x}~{|x|x}}for<M:Modulus><&'_ StaticModInt<M> >~<&'_ StaticModInt<M> >->StaticModInt<M>{{|&x|x}~{|&x|x}}for<I:Id><DynamicModInt<I> >~<DynamicModInt<I> >->DynamicModInt<I>{{|x|x}~{|x|x}}for<I:Id><DynamicModInt<I> >~<&'_ DynamicModInt<I>>->DynamicModInt<I>{{|x|x}~{|&x|x}}for<I:Id><&'_ DynamicModInt<I>>~<DynamicModInt<I> >->DynamicModInt<I>{{|&x|x}~{|x|x}}for<I:Id><&'_ DynamicModInt<I>>~<&'_ DynamicModInt<I>>->DynamicModInt<I>{{|&x|x}~{|&x|x}}for<M:Modulus,T:RemEuclidU32><StaticModInt<M> >~<T>->StaticModInt<M>{{|x|x}~{StaticModInt::<M>::new}}for<I:Id,T:RemEuclidU32><DynamicModInt<I> >~<T>->DynamicModInt<I>{{|x|x}~{DynamicModInt::<I>::new}}}impl_assign_ops!{for<M:Modulus><StaticModInt<M> >~=<StaticModInt<M> >{_~={|x|x}}for<M:Modulus><StaticModInt<M> >~=<&'_ StaticModInt<M> >{_~={|&x|x}}for<I:Id><DynamicModInt<I>>~=<DynamicModInt<I> >{_~={|x|x}}for<I:Id><DynamicModInt<I>>~=<&'_ DynamicModInt<I>>{_~={|&x|x}}for<M:Modulus,T:RemEuclidU32><StaticModInt<M> >~=<T>{_~={StaticModInt::<M>::new}}for<I:Id,T:RemEuclidU32><DynamicModInt<I>>~=<T>{_~={DynamicModInt::<I>::new}}}macro_rules!impl_folding{()=>{};(impl<$generic_param:ident:$generic_param_bound:tt>$trait:ident<_>for$self:ty{fn$method:ident(_)->_{_($unit:expr,$op:expr)}}$($rest:tt)*)=>{impl<$generic_param:$generic_param_bound>$trait<Self>for$self{#[inline]fn$method<S>(iter:S)->Self where S:Iterator<Item=Self>,{iter.fold($unit,$op)}}impl<'a,$generic_param:$generic_param_bound>$trait<&'a Self>for$self{#[inline]fn$method<S>(iter:S)->Self where S:Iterator<Item=&'a Self>,{iter.fold($unit,$op)}}impl_folding!($($rest)*);};}impl_folding!{impl<M:Modulus>Sum<_>for StaticModInt<M>{fn sum(_)->_{_(Self::raw(0),Add::add)}}impl<M:Modulus>Product<_>for StaticModInt<M>{fn product(_)->_{_(Self::raw(1),Mul::mul)}}impl<I:Id>Sum<_>for DynamicModInt<I>{fn sum(_)->_{_(Self::raw(0),Add::add)}}impl<I:Id>Product<_>for DynamicModInt<I>{fn product(_)->_{_(Self::raw(1),Mul::mul)}}}}}
        pub mod __acl_convolution_unwrap_0_1_0 {use crate::__cargo_equip::preludes::__acl_convolution_unwrap_0_1_0::*;macro_rules!modulus{($($name:ident),*)=>{$(#[derive(Copy,Clone,Eq,PartialEq)]enum$name{}impl Modulus for$name{const VALUE:u32=$name as _;const HINT_VALUE_IS_PRIME:bool=true;fn butterfly_cache()->&'static::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<acl_modint::ButterflyCache<Self>>>>{thread_local!{static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<acl_modint::ButterflyCache<$name>>>=::std::default::Default::default();}&BUTTERFLY_CACHE}})*};}use acl_modint::{ButterflyCache,Modulus,RemEuclidU32,StaticModInt};use std::{cmp,convert::{TryFrom,TryInto as _},fmt,};#[allow(clippy::many_single_char_names)]pub fn convolution<M>(a:&[StaticModInt<M>],b:&[StaticModInt<M>])->Vec<StaticModInt<M>>where M:Modulus,{if a.is_empty()||b.is_empty(){return vec![];}let(n,m)=(a.len(),b.len());if cmp::min(n,m)<=60{let(n,m,a,b)=if n<m{(m,n,b,a)}else{(n,m,a,b)};let mut ans=vec![StaticModInt::new(0);n+m-1];for i in 0..n{for j in 0..m{ans[i+j]+=a[i]*b[j];}}return ans;}let(mut a,mut b)=(a.to_owned(),b.to_owned());let z=1<<acl_internal_bit::ceil_pow2((n+m-1)as _);a.resize(z,StaticModInt::raw(0));butterfly(&mut a);b.resize(z,StaticModInt::raw(0));butterfly(&mut b);for(a,b)in a.iter_mut().zip(&b){*a*=b;}butterfly_inv(&mut a);a.resize(n+m-1,StaticModInt::raw(0));let iz=StaticModInt::new(z).inv();for a in&mut a{*a*=iz;}a}pub fn convolution_raw<T,M>(a:&[T],b:&[T])->Vec<T>where T:RemEuclidU32+TryFrom<u32>+Clone,T::Error:fmt::Debug,M:Modulus,{let a=a.iter().cloned().map(Into::into).collect::<Vec<_>>();let b=b.iter().cloned().map(Into::into).collect::<Vec<_>>();convolution::<M>(&a,&b).into_iter().map(|z|{z.val().try_into().expect("the numeric type is smaller than the modulus")}).collect()}#[allow(clippy::many_single_char_names)]pub fn convolution_i64(a:&[i64],b:&[i64])->Vec<i64>{const M1:u64=754_974_721;const M2:u64=167_772_161;const M3:u64=469_762_049;const M2M3:u64=M2*M3;const M1M3:u64=M1*M3;const M1M2:u64=M1*M2;const M1M2M3:u64=M1M2.wrapping_mul(M3);modulus!(M1,M2,M3);if a.is_empty()||b.is_empty(){return vec![];}let(_,i1)=acl_internal_math::inv_gcd(M2M3 as _,M1 as _);let(_,i2)=acl_internal_math::inv_gcd(M1M3 as _,M2 as _);let(_,i3)=acl_internal_math::inv_gcd(M1M2 as _,M3 as _);let c1=convolution_raw::<i64,M1>(a,b);let c2=convolution_raw::<i64,M2>(a,b);let c3=convolution_raw::<i64,M3>(a,b);c1.into_iter().zip(c2).zip(c3).map(|((c1,c2),c3)|{const OFFSET:&[u64]=&[0,0,M1M2M3,2*M1M2M3,3*M1M2M3];let mut x=[(c1,i1,M1,M2M3),(c2,i2,M2,M1M3),(c3,i3,M3,M1M2)].iter().map(|&(c,i,m1,m2)|c.wrapping_mul(i).rem_euclid(m1 as _).wrapping_mul(m2 as _)).fold(0,i64::wrapping_add);let mut diff=c1-acl_internal_math::safe_mod(x,M1 as _);if diff<0{diff+=M1 as i64;}x=x.wrapping_sub(OFFSET[diff.rem_euclid(5)as usize]as _);x}).collect()}#[allow(clippy::many_single_char_names)]pub fn butterfly<M:Modulus>(a:&mut[StaticModInt<M>]){let n=a.len();let h=acl_internal_bit::ceil_pow2(n as u32);M::butterfly_cache().with(|cache|{let mut cache=cache.borrow_mut();let ButterflyCache{sum_e,..}=cache.get_or_insert_with(prepare);for ph in 1..=h{let w=1<<(ph-1);let p=1<<(h-ph);let mut now=StaticModInt::<M>::new(1);for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=a[i+offset];let r=a[i+offset+p]*now;a[i+offset]=l+r;a[i+offset+p]=l-r;}now*=sum_e[(!s).trailing_zeros()as usize];}}});}#[allow(clippy::many_single_char_names)]pub fn butterfly_inv<M:Modulus>(a:&mut[StaticModInt<M>]){let n=a.len();let h=acl_internal_bit::ceil_pow2(n as u32);M::butterfly_cache().with(|cache|{let mut cache=cache.borrow_mut();let ButterflyCache{sum_ie,..}=cache.get_or_insert_with(prepare);for ph in(1..=h).rev(){let w=1<<(ph-1);let p=1<<(h-ph);let mut inow=StaticModInt::<M>::new(1);for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=a[i+offset];let r=a[i+offset+p];a[i+offset]=l+r;a[i+offset+p]=StaticModInt::new(M::VALUE+l.val()-r.val())*inow;}inow*=sum_ie[(!s).trailing_zeros()as usize];}}});}fn prepare<M:Modulus>()->ButterflyCache<M>{let g=StaticModInt::<M>::raw(acl_internal_math::primitive_root(M::VALUE as i32)as u32);let mut es=[StaticModInt::<M>::raw(0);30];let mut ies=[StaticModInt::<M>::raw(0);30];let cnt2=(M::VALUE-1).trailing_zeros()as usize;let mut e=g.pow(((M::VALUE-1)>>cnt2).into());let mut ie=e.inv();for i in(2..=cnt2).rev(){es[i-2]=e;ies[i-2]=ie;e*=e;ie*=ie;}let sum_e=es.iter().scan(StaticModInt::new(1),|acc,e|{*acc*=e;Some(*acc)}).collect();let sum_ie=ies.iter().scan(StaticModInt::new(1),|acc,ie|{*acc*=ie;Some(*acc)}).collect();ButterflyCache{sum_e,sum_ie}}}
        pub mod proth_fps {use crate::__cargo_equip::preludes::proth_fps::*;mod fps{use crate::__cargo_equip::preludes::proth_fps::*;use acl_convolution_unwrap::{butterfly,convolution};use acl_modint::{Modulus,StaticModInt as Mint};use std::{fmt::Display,ops::{Add,AddAssign,Div,DivAssign,Index,IndexMut,Mul,MulAssign,Neg,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},slice::SliceIndex,};#[derive(Debug,PartialEq,Eq,Clone)]pub struct FormalPowerSeries<Coeff>(Vec<Coeff>);type Fps<M> =FormalPowerSeries<Mint<M>>;use crate::__cargo_equip::crates::proth_fps::NttFrequencySpectrum as Freq;impl<M:Modulus>FormalPowerSeries<Mint<M>>{pub fn from_vec(f:Vec<Mint<M>>)->Self{Self(f)}pub fn shrink(&mut self){let f=&mut self.0;while f.last()==Some(&Mint::raw(0)){f.pop();}}pub fn len(&self)->usize{self.0.len()}pub fn is_empty(&self)->bool{self.0.is_empty()}pub fn differentiate(&mut self){if self.is_empty(){return;}for(i,a)in self.0.iter_mut().enumerate().skip(1){*a*=i;}self.0.remove(0);}pub fn integrate(&mut self){let n=self.len();let mut facts=vec![Mint::new(1);n+1];for i in 0..n{facts[i+1]=facts[i]*(i+1);}let facts=facts;let mut inv_fact=facts[n].inv();self.0.push(0.into());for i in(1..=n).rev(){debug_assert_eq!(inv_fact,facts[i].inv());self.0[i]=self.0[i-1]*facts[i-1]*inv_fact;inv_fact*=i;}self.0[0]=0.into();}pub fn reverse(&mut self){self.0.reverse();}pub fn differentiated(&self)->Self{let mut f=self.clone();f.differentiate();f}pub fn integrated(&self)->Self{let mut f=self.clone();f.integrate();f}pub fn reversed(&self)->Self{let mut f=self.clone();f.reverse();f}pub fn resize(&mut self,new_len:usize){self.0.resize(new_len,0.into());}pub fn prefix(&self,len:usize)->Self{if len<=self.len(){self.0[..len].to_owned().into()}else{let mut f=self.clone();f.resize(len);f}}pub fn negate(&mut self){for ai in self.0.iter_mut(){*ai=-*ai;}}pub fn into_ntt(mut self)->Freq<Mint<M>>{butterfly(&mut self.0);Freq::from_vec(self.0)}pub fn fact_mul(&mut self){let mut fact=Mint::new(1);for(i,a)in self.0.iter_mut().enumerate(){*a*=fact;fact*=i+1;}}pub fn fact_div(&mut self){let mut fact=Mint::new(1);for i in 1..self.len(){fact*=i;}fact=fact.inv();for(i,a)in self.0.iter_mut().enumerate().rev(){*a*=fact;fact*=i;}}pub fn fact_muled(&self)->Self{let mut f=self.clone();f.fact_mul();f}pub fn fact_dived(&self)->Self{let mut f=self.clone();f.fact_div();f}pub fn inv_until(&self,len:usize)->Self{assert!(!self.is_empty()&&self[0]!=Mint::raw(0),"inv does not exist",);if len==0{return Self::default();}let mut g=Self::from_vec(vec![self[0].inv()]);while g.len()<len{let m=g.len();let f=self.prefix(m*2);let gq=g.prefix(m*2).into_ntt();let fq=f.into_ntt();let mut h=Fps::from_vec((fq*&gq).into_intt()[m..m*2].to_vec());h.resize(m*2);let hg=(-h.into_ntt()*gq).into_intt();g.0.splice(m..m,hg[..m].to_vec());}g.resize(len);g}pub fn exp_until(&self,len:usize)->Self{if self.is_empty(){let mut f=Self::from(vec![1]);f.resize(len);return f;}assert_eq!(self[0],0.into(),"F[0]({}) must be 0",self[0]);if len==0{return Self::default();}let mut g=Self::from(vec![1]);while g.len()<len{let m=g.len();let f=self.prefix(m*2);g=(Mint::new(1)+f-g.log_until(m*2))*g;g.resize(m*2);}g.resize(len);g}pub fn log_until(&self,len:usize)->Self{assert!(!self.is_empty(),"len must be greater than 0");assert_eq!(self[0],1.into(),"F[0]({}) must be 1",self[0]);if len==0{return Self::default();}let mut g=self.differentiated()*self.inv_until(len);g.integrate();g.resize(len);g}pub fn pow_until(&self,e:u64,len:usize)->Self{if len==0{return Self::default();}if e==0{return Self::from(vec![1]).prefix(len);}match self.0.iter().enumerate().find(|(_,a)|**a!=0.into()){Some((l,al))if l==0||e<((len+l-1)/l)as u64=>{let g=(self>>l)/al;let zeros=((l as u64)*e)as usize;let rem_len=len-zeros;(al.pow(e)*(g.log_until(rem_len)*Mint::new(e)).exp())<<zeros}_=>vec![0;len].into(),}}pub fn sqrt_until(&self,_len:usize)->Option<Self>{todo!()}pub fn inv(&self)->Self{self.inv_until(self.len())}pub fn exp(&self)->Self{self.exp_until(self.len())}pub fn log(&self)->Self{self.log_until(self.len())}pub fn pow(&self,e:u64)->Self{self.pow_until(e,self.len())}pub fn sqrt(&self)->Option<Self>{self.sqrt_until(self.len())}pub fn eval<I:Into<Mint<M>>>(&self,a:I)->Mint<M>{let a=a.into();if self.is_empty(){Mint::raw(0)}else if a==Mint::raw(0){self[0]}else{let mut p=Mint::raw(1);let mut ans=Mint::raw(0);for i in 0..self.len(){ans+=p*self[i];p*=a;}ans}}pub fn of_ax<I:Into<Mint<M>>>(mut self,a:I)->Self{let a=a.into();let mut pa=Mint::new(1);if a==pa{return self;}if a==-pa{for e in self.0.iter_mut().skip(1).step_by(2){*e=-*e;}return self;}for e in self.0.iter_mut(){*e*=pa;pa*=a;}self}pub fn of_linear<Ia:Into<Mint<M>>,Ib:Into<Mint<M>>>(mut self,a:Ia,b:Ib)->Self{let a=Into::<Mint<_>>::into(a);let b=Into::<Mint<_>>::into(b);let n=self.len();if b.val()!=0{self.fact_mul();self.reverse();let bp={let mut bp=Fps::from(vec![1;n]).of_ax(b);bp.fact_div();bp};self*=bp;self.resize(n);self.reverse();self.fact_div();}self.of_ax(a)}pub fn poly_div(&self,g:&Self)->Self{let mut f=self.clone();f.shrink();let mut g=g.clone();g.shrink();let n=f.len();let m=g.len();assert_ne!(m,0,"divide by 0");if m==1{return f/g[0];}if n<m{return Self::default();}let l=n-m+1;f.reverse();g.reverse();let mut q=(&f*g.inv_until(l)).prefix(l);q.reverse();q}pub fn poly_mod(&self,g:&Self)->Self{let mut f=self.clone();f.shrink();let mut g=g.clone();g.shrink();let n=f.len();let m=g.len();assert_ne!(m,0,"divide by 0");if m==1{return Self::default();}if n<m{return f;}let l=n-m+1;f.reverse();g.reverse();let mut q=(&f*g.inv_until(l)).prefix(l);f.reverse();g.reverse();q.reverse();let mut r=f-g*&q;r.shrink();r}pub fn poly_divmod(&self,g:&Self)->(Self,Self){let mut f=self.clone();f.shrink();let mut g=g.clone();g.shrink();let n=f.len();let m=g.len();assert_ne!(m,0,"divide by 0");if m==1{return(f/g[0],Self::default());}if n<m{return(Self::default(),f);}let l=n-m+1;f.reverse();g.reverse();let mut q=(&f*g.inv_until(l)).prefix(l);f.reverse();g.reverse();q.reverse();let mut r=f-g*&q;r.shrink();(q,r)}}impl<M,I>From<Vec<I>>for Fps<M>where M:Modulus,I:Clone+Into<Mint<M>>,{fn from(a:Vec<I>)->Self{Self::from_vec(a.iter().map(|ai|ai.clone().into()).collect::<Vec<_>>())}}impl<M>From<Fps<M>>for Vec<Mint<M>>{fn from(value:Fps<M>)->Vec<Mint<M>>{value.0}}impl<M:Modulus>Display for Fps<M>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0.iter().map(|a|format!("{}",a)).collect::<Vec<_>>().join(" "))}}impl<M:Modulus>Default for Fps<M>{fn default()->Self{Self::from_vec(vec![])}}impl<M:Modulus>Add<Fps<M>>for Fps<M>{type Output=Fps<M>;fn add(mut self,rhs:Fps<M>)->Self::Output{self+=&rhs;self}}impl<M:Modulus>Add<&Fps<M>>for Fps<M>{type Output=Fps<M>;fn add(mut self,rhs:&Fps<M>)->Self::Output{self+=rhs;self}}impl<M:Modulus>Add<Fps<M>>for&Fps<M>{type Output=Fps<M>;fn add(self,mut rhs:Fps<M>)->Self::Output{rhs+=self;rhs}}impl<M:Modulus>Add<&Fps<M>>for&Fps<M>{type Output=Fps<M>;fn add(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=self;rhs}}impl<M:Modulus>AddAssign<Fps<M>>for Fps<M>{fn add_assign(&mut self,rhs:Fps<M>){*self+=&rhs;}}impl<M:Modulus>AddAssign<&Fps<M>>for Fps<M>{fn add_assign(&mut self,rhs:&Fps<M>){if self.len()<rhs.len(){self.resize(rhs.len());}for(a,b)in self.0.iter_mut().zip(rhs.0.iter()){*a+=b;}}}impl<M:Modulus>Add<Mint<M>>for Fps<M>{type Output=Fps<M>;fn add(mut self,rhs:Mint<M>)->Self::Output{self+=&rhs;self}}impl<M:Modulus>Add<&Mint<M>>for Fps<M>{type Output=Fps<M>;fn add(mut self,rhs:&Mint<M>)->Self::Output{self+=rhs;self}}impl<M:Modulus>Add<Mint<M>>for&Fps<M>{type Output=Fps<M>;fn add(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f+=&rhs;f}}impl<M:Modulus>Add<&Mint<M>>for&Fps<M>{type Output=Fps<M>;fn add(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f+=rhs;f}}impl<M:Modulus>AddAssign<Mint<M>>for Fps<M>{fn add_assign(&mut self,rhs:Mint<M>){*self+=&rhs;}}impl<M:Modulus>AddAssign<&Mint<M>>for Fps<M>{fn add_assign(&mut self,rhs:&Mint<M>){if self.is_empty(){self.0.push(*rhs);}else{self[0]+=rhs;}}}impl<M:Modulus>Add<Fps<M>>for Mint<M>{type Output=Fps<M>;fn add(self,mut rhs:Fps<M>)->Self::Output{rhs+=&self;rhs}}impl<M:Modulus>Add<&Fps<M>>for Mint<M>{type Output=Fps<M>;fn add(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=&self;rhs}}impl<M:Modulus>Add<Fps<M>>for&Mint<M>{type Output=Fps<M>;fn add(self,mut rhs:Fps<M>)->Self::Output{rhs+=self;rhs}}impl<M:Modulus>Add<&Fps<M>>for&Mint<M>{type Output=Fps<M>;fn add(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=self;rhs}}impl<M:Modulus>Sub<Fps<M>>for Fps<M>{type Output=Fps<M>;fn sub(mut self,rhs:Fps<M>)->Self::Output{self-=&rhs;self}}impl<M:Modulus>Sub<&Fps<M>>for Fps<M>{type Output=Fps<M>;fn sub(mut self,rhs:&Fps<M>)->Self::Output{self-=rhs;self}}impl<M:Modulus>Sub<Fps<M>>for&Fps<M>{type Output=Fps<M>;fn sub(self,mut rhs:Fps<M>)->Self::Output{rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Fps<M>>for&Fps<M>{type Output=Fps<M>;fn sub(self,rhs:&Fps<M>)->Self::Output{let mut f=self.clone();f-=rhs;f}}impl<M:Modulus>SubAssign<Fps<M>>for Fps<M>{fn sub_assign(&mut self,rhs:Fps<M>){*self-=&rhs;}}impl<M:Modulus>SubAssign<&Fps<M>>for Fps<M>{fn sub_assign(&mut self,rhs:&Fps<M>){if self.len()<rhs.len(){self.resize(rhs.len());}for(a,b)in self.0.iter_mut().zip(rhs.0.iter()){*a-=b;}}}impl<M:Modulus>Sub<Mint<M>>for Fps<M>{type Output=Fps<M>;fn sub(mut self,rhs:Mint<M>)->Self::Output{self-=&rhs;self}}impl<M:Modulus>Sub<&Mint<M>>for Fps<M>{type Output=Fps<M>;fn sub(mut self,rhs:&Mint<M>)->Self::Output{self-=rhs;self}}impl<M:Modulus>Sub<Mint<M>>for&Fps<M>{type Output=Fps<M>;fn sub(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f-=&rhs;f}}impl<M:Modulus>Sub<&Mint<M>>for&Fps<M>{type Output=Fps<M>;fn sub(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f-=rhs;f}}impl<M:Modulus>SubAssign<Mint<M>>for Fps<M>{fn sub_assign(&mut self,rhs:Mint<M>){*self-=&rhs;}}impl<M:Modulus>SubAssign<&Mint<M>>for Fps<M>{fn sub_assign(&mut self,rhs:&Mint<M>){if self.is_empty(){self.0.push(-rhs);}else{self[0]-=rhs;}}}impl<M:Modulus>Sub<Fps<M>>for Mint<M>{type Output=Fps<M>;fn sub(self,mut rhs:Fps<M>)->Self::Output{rhs-=&self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Fps<M>>for Mint<M>{type Output=Fps<M>;fn sub(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs-=&self;rhs.negate();rhs}}impl<M:Modulus>Sub<Fps<M>>for&Mint<M>{type Output=Fps<M>;fn sub(self,mut rhs:Fps<M>)->Self::Output{rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Fps<M>>for&Mint<M>{type Output=Fps<M>;fn sub(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Mul<Fps<M>>for Fps<M>{type Output=Fps<M>;fn mul(self,rhs:Fps<M>)->Self::Output{&self*&rhs}}impl<M:Modulus>Mul<&Fps<M>>for Fps<M>{type Output=Fps<M>;fn mul(self,rhs:&Fps<M>)->Self::Output{&self*rhs}}impl<M:Modulus>Mul<Fps<M>>for&Fps<M>{type Output=Fps<M>;fn mul(self,rhs:Fps<M>)->Self::Output{self*&rhs}}impl<M:Modulus>Mul<&Fps<M>>for&Fps<M>{type Output=Fps<M>;fn mul(self,rhs:&Fps<M>)->Self::Output{Self::Output::from_vec(convolution(&self.0,&rhs.0))}}impl<M:Modulus>MulAssign<Fps<M>>for Fps<M>{fn mul_assign(&mut self,rhs:Fps<M>){*self=&*self*&rhs;}}impl<M:Modulus>MulAssign<&Fps<M>>for Fps<M>{fn mul_assign(&mut self,rhs:&Fps<M>){*self=&*self*rhs;}}impl<M:Modulus>Mul<Mint<M>>for Fps<M>{type Output=Fps<M>;fn mul(mut self,rhs:Mint<M>)->Self::Output{self*=rhs;self}}impl<M:Modulus>Mul<&Mint<M>>for Fps<M>{type Output=Fps<M>;fn mul(mut self,rhs:&Mint<M>)->Self::Output{self*=*rhs;self}}impl<M:Modulus>Mul<Mint<M>>for&Fps<M>{type Output=Fps<M>;fn mul(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f*=rhs;f}}impl<M:Modulus>Mul<&Mint<M>>for&Fps<M>{type Output=Fps<M>;fn mul(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f*=*rhs;f}}impl<M:Modulus>MulAssign<Mint<M>>for Fps<M>{fn mul_assign(&mut self,rhs:Mint<M>){if rhs==Mint::new(1){return;}if rhs+1==Mint::raw(0){self.negate();return;}for a in self.0.iter_mut(){*a*=rhs}}}impl<M:Modulus>MulAssign<&Mint<M>>for Fps<M>{fn mul_assign(&mut self,rhs:&Mint<M>){*self*=*rhs;}}impl<M:Modulus>Mul<Fps<M>>for Mint<M>{type Output=Fps<M>;fn mul(self,mut rhs:Fps<M>)->Self::Output{rhs*=self;rhs}}impl<M:Modulus>Mul<&Fps<M>>for Mint<M>{type Output=Fps<M>;fn mul(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs*=self;rhs}}impl<M:Modulus>Mul<Fps<M>>for&Mint<M>{type Output=Fps<M>;fn mul(self,mut rhs:Fps<M>)->Self::Output{rhs*=*self;rhs}}impl<M:Modulus>Mul<&Fps<M>>for&Mint<M>{type Output=Fps<M>;fn mul(self,rhs:&Fps<M>)->Self::Output{let mut rhs=rhs.clone();rhs*=*self;rhs}}impl<M:Modulus>Div<Mint<M>>for Fps<M>{type Output=Fps<M>;fn div(mut self,rhs:Mint<M>)->Self::Output{self/=&rhs;self}}impl<M:Modulus>Div<&Mint<M>>for Fps<M>{type Output=Fps<M>;fn div(mut self,rhs:&Mint<M>)->Self::Output{self/=rhs;self}}impl<M:Modulus>Div<Mint<M>>for&Fps<M>{type Output=Fps<M>;fn div(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f/=&rhs;f}}impl<M:Modulus>Div<&Mint<M>>for&Fps<M>{type Output=Fps<M>;fn div(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f/=rhs;f}}impl<M:Modulus>DivAssign<Mint<M>>for Fps<M>{fn div_assign(&mut self,rhs:Mint<M>){*self/=&rhs;}}impl<M:Modulus>DivAssign<&Mint<M>>for Fps<M>{#[allow(clippy::suspicious_op_assign_impl)]fn div_assign(&mut self,rhs:&Mint<M>){*self*=rhs.inv();}}impl<M:Modulus,Idx>Index<Idx>for Fps<M>where Idx:SliceIndex<[Mint<M>]>,{type Output=<Idx as SliceIndex<[Mint<M>]>>::Output;fn index(&self,index:Idx)->&Self::Output{&self.0[index]}}impl<M:Modulus,Idx>IndexMut<Idx>for Fps<M>where Idx:SliceIndex<[Mint<M>]>,{fn index_mut(&mut self,index:Idx)->&mut Self::Output{&mut self.0[index]}}impl<M:Modulus>Neg for Fps<M>{type Output=Fps<M>;fn neg(mut self)->Self::Output{self.negate();self}}impl<M:Modulus>Neg for&Fps<M>{type Output=Fps<M>;fn neg(self)->Self::Output{let f=self.clone();-f}}impl<M:Modulus>Shl<usize>for Fps<M>{type Output=Self;fn shl(mut self,rhs:usize)->Self::Output{self<<=rhs;self}}impl<M:Modulus>Shl<usize>for&Fps<M>{type Output=Fps<M>;fn shl(self,rhs:usize)->Self::Output{let mut f=self.clone();f<<=rhs;f}}impl<M:Modulus>ShlAssign<usize>for Fps<M>{fn shl_assign(&mut self,rhs:usize){self.0.splice(0..0,vec![0.into();rhs]);}}impl<M:Modulus>Shr<usize>for Fps<M>{type Output=Self;fn shr(mut self,rhs:usize)->Self::Output{self>>=rhs;self}}impl<M:Modulus>Shr<usize>for&Fps<M>{type Output=Fps<M>;fn shr(self,rhs:usize)->Self::Output{let mut f=self.clone();f>>=rhs;f}}impl<M:Modulus>ShrAssign<usize>for Fps<M>{fn shr_assign(&mut self,rhs:usize){self.0.splice(0..rhs.min(self.len()),vec![]);}}}mod freq{use crate::__cargo_equip::preludes::proth_fps::*;use acl_convolution_unwrap::butterfly_inv;use acl_modint::{Modulus,StaticModInt as Mint};use std::{fmt::Display,ops::{Add,AddAssign,Div,DivAssign,Index,IndexMut,Mul,MulAssign,Neg,Sub,SubAssign,},slice::SliceIndex,};use crate::__cargo_equip::crates::proth_fps::FormalPowerSeries as Fps;#[derive(Debug,PartialEq,Eq,Clone)]pub struct NttFrequencySpectrum<Coeff>(Vec<Coeff>);type Freq<M> =NttFrequencySpectrum<Mint<M>>;impl<M:Modulus>NttFrequencySpectrum<Mint<M>>{pub fn from_vec(f:Vec<Mint<M>>)->Self{Self(f)}pub fn len(&self)->usize{self.0.len()}pub fn is_empty(&self)->bool{self.0.is_empty()}pub fn resize(&mut self,new_len:usize){self.0.resize(new_len,0.into());}pub fn prefix(&self,len:usize)->Self{if len<=self.len(){self.0[..len].to_owned().into()}else{let mut f=self.clone();f.resize(len);f}}pub fn negate(&mut self){for ai in self.0.iter_mut(){*ai=-*ai;}}pub fn into_intt(mut self)->Fps<Mint<M>>{butterfly_inv(&mut self.0);self/=Mint::new(self.len());Fps::from_vec(self.0)}}impl<M,I>From<Vec<I>>for Freq<M>where M:Modulus,I:Clone+Into<Mint<M>>,{fn from(a:Vec<I>)->Self{Self::from_vec(a.iter().map(|ai|ai.clone().into()).collect::<Vec<_>>())}}impl<M:Modulus>Display for Freq<M>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0.iter().map(|a|format!("{}",a)).collect::<Vec<_>>().join(" "))}}impl<M:Modulus>Default for Freq<M>{fn default()->Self{Self::from_vec(vec![])}}impl<M:Modulus>Add<Freq<M>>for Freq<M>{type Output=Freq<M>;fn add(mut self,rhs:Freq<M>)->Self::Output{self+=&rhs;self}}impl<M:Modulus>Add<&Freq<M>>for Freq<M>{type Output=Freq<M>;fn add(mut self,rhs:&Freq<M>)->Self::Output{self+=rhs;self}}impl<M:Modulus>Add<Freq<M>>for&Freq<M>{type Output=Freq<M>;fn add(self,mut rhs:Freq<M>)->Self::Output{rhs+=self;rhs}}impl<M:Modulus>Add<&Freq<M>>for&Freq<M>{type Output=Freq<M>;fn add(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=self;rhs}}impl<M:Modulus>AddAssign<Freq<M>>for Freq<M>{fn add_assign(&mut self,rhs:Freq<M>){*self+=&rhs;}}impl<M:Modulus>AddAssign<&Freq<M>>for Freq<M>{fn add_assign(&mut self,rhs:&Freq<M>){assert_eq!(self.len(),rhs.len(),"[NttFrequencySpectrum] addition of different length: ({}) + ({})",self.len(),rhs.len());for(a,b)in self.0.iter_mut().zip(rhs.0.iter()){*a+=b;}}}impl<M:Modulus>Add<Mint<M>>for Freq<M>{type Output=Freq<M>;fn add(mut self,rhs:Mint<M>)->Self::Output{self+=&rhs;self}}impl<M:Modulus>Add<&Mint<M>>for Freq<M>{type Output=Freq<M>;fn add(mut self,rhs:&Mint<M>)->Self::Output{self+=rhs;self}}impl<M:Modulus>Add<Mint<M>>for&Freq<M>{type Output=Freq<M>;fn add(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f+=&rhs;f}}impl<M:Modulus>Add<&Mint<M>>for&Freq<M>{type Output=Freq<M>;fn add(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f+=rhs;f}}impl<M:Modulus>AddAssign<Mint<M>>for Freq<M>{fn add_assign(&mut self,rhs:Mint<M>){*self+=&rhs;}}impl<M:Modulus>AddAssign<&Mint<M>>for Freq<M>{fn add_assign(&mut self,rhs:&Mint<M>){for a in self.0.iter_mut(){*a+=rhs;}}}impl<M:Modulus>Add<Freq<M>>for Mint<M>{type Output=Freq<M>;fn add(self,mut rhs:Freq<M>)->Self::Output{rhs+=&self;rhs}}impl<M:Modulus>Add<&Freq<M>>for Mint<M>{type Output=Freq<M>;fn add(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=&self;rhs}}impl<M:Modulus>Add<Freq<M>>for&Mint<M>{type Output=Freq<M>;fn add(self,mut rhs:Freq<M>)->Self::Output{rhs+=self;rhs}}impl<M:Modulus>Add<&Freq<M>>for&Mint<M>{type Output=Freq<M>;fn add(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs+=self;rhs}}impl<M:Modulus>Sub<Freq<M>>for Freq<M>{type Output=Freq<M>;fn sub(mut self,rhs:Freq<M>)->Self::Output{self-=&rhs;self}}impl<M:Modulus>Sub<&Freq<M>>for Freq<M>{type Output=Freq<M>;fn sub(mut self,rhs:&Freq<M>)->Self::Output{self-=rhs;self}}impl<M:Modulus>Sub<Freq<M>>for&Freq<M>{type Output=Freq<M>;fn sub(self,mut rhs:Freq<M>)->Self::Output{rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Freq<M>>for&Freq<M>{type Output=Freq<M>;fn sub(self,rhs:&Freq<M>)->Self::Output{let mut f=self.clone();f-=rhs;f}}impl<M:Modulus>SubAssign<Freq<M>>for Freq<M>{fn sub_assign(&mut self,rhs:Freq<M>){*self-=&rhs;}}impl<M:Modulus>SubAssign<&Freq<M>>for Freq<M>{fn sub_assign(&mut self,rhs:&Freq<M>){assert_eq!(self.len(),rhs.len(),"[NttFrequencySpectrum] subtraction of different length: ({}) - ({})",self.len(),rhs.len());for(a,b)in self.0.iter_mut().zip(rhs.0.iter()){*a-=b;}}}impl<M:Modulus>Sub<Mint<M>>for Freq<M>{type Output=Freq<M>;fn sub(mut self,rhs:Mint<M>)->Self::Output{self-=&rhs;self}}impl<M:Modulus>Sub<&Mint<M>>for Freq<M>{type Output=Freq<M>;fn sub(mut self,rhs:&Mint<M>)->Self::Output{self-=rhs;self}}impl<M:Modulus>Sub<Mint<M>>for&Freq<M>{type Output=Freq<M>;fn sub(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f-=&rhs;f}}impl<M:Modulus>Sub<&Mint<M>>for&Freq<M>{type Output=Freq<M>;fn sub(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f-=rhs;f}}impl<M:Modulus>SubAssign<Mint<M>>for Freq<M>{fn sub_assign(&mut self,rhs:Mint<M>){*self-=&rhs;}}impl<M:Modulus>SubAssign<&Mint<M>>for Freq<M>{fn sub_assign(&mut self,rhs:&Mint<M>){for a in self.0.iter_mut(){*a-=rhs;}}}impl<M:Modulus>Sub<Freq<M>>for Mint<M>{type Output=Freq<M>;fn sub(self,mut rhs:Freq<M>)->Self::Output{rhs-=&self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Freq<M>>for Mint<M>{type Output=Freq<M>;fn sub(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs-=&self;rhs.negate();rhs}}impl<M:Modulus>Sub<Freq<M>>for&Mint<M>{type Output=Freq<M>;fn sub(self,mut rhs:Freq<M>)->Self::Output{rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Sub<&Freq<M>>for&Mint<M>{type Output=Freq<M>;fn sub(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs-=self;rhs.negate();rhs}}impl<M:Modulus>Mul<Freq<M>>for Freq<M>{type Output=Freq<M>;fn mul(mut self,rhs:Freq<M>)->Self::Output{self*=&rhs;self}}impl<M:Modulus>Mul<&Freq<M>>for Freq<M>{type Output=Freq<M>;fn mul(mut self,rhs:&Freq<M>)->Self::Output{self*=rhs;self}}impl<M:Modulus>Mul<Freq<M>>for&Freq<M>{type Output=Freq<M>;fn mul(self,mut rhs:Freq<M>)->Self::Output{rhs*=self;rhs}}impl<M:Modulus>Mul<&Freq<M>>for&Freq<M>{type Output=Freq<M>;fn mul(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs*=self;rhs}}impl<M:Modulus>MulAssign<Freq<M>>for Freq<M>{fn mul_assign(&mut self,rhs:Freq<M>){*self*=&rhs;}}impl<M:Modulus>MulAssign<&Freq<M>>for Freq<M>{fn mul_assign(&mut self,rhs:&Freq<M>){assert_eq!(self.len(),rhs.len(),"[NttFrequencySpectrum] multiplication of different length: ({}) * ({})",self.len(),rhs.len());for(a,b)in self.0.iter_mut().zip(rhs.0.iter()){*a*=b;}}}impl<M:Modulus>Mul<Mint<M>>for Freq<M>{type Output=Freq<M>;fn mul(mut self,rhs:Mint<M>)->Self::Output{self*=rhs;self}}impl<M:Modulus>Mul<&Mint<M>>for Freq<M>{type Output=Freq<M>;fn mul(mut self,rhs:&Mint<M>)->Self::Output{self*=*rhs;self}}impl<M:Modulus>Mul<Mint<M>>for&Freq<M>{type Output=Freq<M>;fn mul(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f*=rhs;f}}impl<M:Modulus>Mul<&Mint<M>>for&Freq<M>{type Output=Freq<M>;fn mul(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f*=*rhs;f}}impl<M:Modulus>MulAssign<Mint<M>>for Freq<M>{fn mul_assign(&mut self,rhs:Mint<M>){if rhs==Mint::new(1){return;}if rhs+1==Mint::raw(0){self.negate();return;}for a in self.0.iter_mut(){*a*=rhs}}}impl<M:Modulus>MulAssign<&Mint<M>>for Freq<M>{fn mul_assign(&mut self,rhs:&Mint<M>){*self*=*rhs;}}impl<M:Modulus>Mul<Freq<M>>for Mint<M>{type Output=Freq<M>;fn mul(self,mut rhs:Freq<M>)->Self::Output{rhs*=self;rhs}}impl<M:Modulus>Mul<&Freq<M>>for Mint<M>{type Output=Freq<M>;fn mul(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs*=self;rhs}}impl<M:Modulus>Mul<Freq<M>>for&Mint<M>{type Output=Freq<M>;fn mul(self,mut rhs:Freq<M>)->Self::Output{rhs*=*self;rhs}}impl<M:Modulus>Mul<&Freq<M>>for&Mint<M>{type Output=Freq<M>;fn mul(self,rhs:&Freq<M>)->Self::Output{let mut rhs=rhs.clone();rhs*=*self;rhs}}impl<M:Modulus>Div<Mint<M>>for Freq<M>{type Output=Freq<M>;fn div(mut self,rhs:Mint<M>)->Self::Output{self/=&rhs;self}}impl<M:Modulus>Div<&Mint<M>>for Freq<M>{type Output=Freq<M>;fn div(mut self,rhs:&Mint<M>)->Self::Output{self/=rhs;self}}impl<M:Modulus>Div<Mint<M>>for&Freq<M>{type Output=Freq<M>;fn div(self,rhs:Mint<M>)->Self::Output{let mut f=self.clone();f/=&rhs;f}}impl<M:Modulus>Div<&Mint<M>>for&Freq<M>{type Output=Freq<M>;fn div(self,rhs:&Mint<M>)->Self::Output{let mut f=self.clone();f/=rhs;f}}impl<M:Modulus>DivAssign<Mint<M>>for Freq<M>{fn div_assign(&mut self,rhs:Mint<M>){*self/=&rhs;}}impl<M:Modulus>DivAssign<&Mint<M>>for Freq<M>{#[allow(clippy::suspicious_op_assign_impl)]fn div_assign(&mut self,rhs:&Mint<M>){*self*=rhs.inv();}}impl<M:Modulus,Idx>Index<Idx>for Freq<M>where Idx:SliceIndex<[Mint<M>]>,{type Output=<Idx as SliceIndex<[Mint<M>]>>::Output;fn index(&self,index:Idx)->&Self::Output{&self.0[index]}}impl<M:Modulus,Idx>IndexMut<Idx>for Freq<M>where Idx:SliceIndex<[Mint<M>]>,{fn index_mut(&mut self,index:Idx)->&mut Self::Output{&mut self.0[index]}}impl<M:Modulus>Neg for Freq<M>{type Output=Freq<M>;fn neg(mut self)->Self::Output{self.negate();self}}impl<M:Modulus>Neg for&Freq<M>{type Output=Freq<M>;fn neg(self)->Self::Output{let f=self.clone();-f}}}pub use fps::FormalPowerSeries;pub use freq::NttFrequencySpectrum;}
    }

    pub(crate) mod macros {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_math_0_1_0 {}
        pub mod acl_modint {}
        pub mod __acl_convolution_unwrap_0_1_0 {}
        pub mod proth_fps {}
    }

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

    mod preludes {
        pub mod __ac_library_rs_parted_internal_bit_0_1_0 {}
        pub mod __ac_library_rs_parted_internal_math_0_1_0 {}
        pub mod acl_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0 as __acl_internal_math;}
        pub mod __acl_convolution_unwrap_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as acl_internal_bit,__ac_library_rs_parted_internal_math_0_1_0 as acl_internal_math,acl_modint};}
        pub mod proth_fps {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__acl_convolution_unwrap_0_1_0 as acl_convolution_unwrap,acl_modint};}
    }
}

Submission Info

Judge Result