結果
| 問題 | No.2798 Multiple Chain |
| ユーザー |
 37kt
|
| 提出日時 | 2024-11-25 09:40:48 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 44,040 bytes |
| コンパイル時間 | 15,744 ms |
| コンパイル使用メモリ | 384,288 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-25 09:41:15 |
| 合計ジャッジ時間 | 17,491 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 1 ms
6,820 KB |
| testcase_02 | AC | 1 ms
6,816 KB |
| testcase_03 | AC | 1 ms
6,820 KB |
| testcase_04 | AC | 1 ms
6,820 KB |
| testcase_05 | AC | 1 ms
6,816 KB |
| testcase_06 | AC | 1 ms
6,820 KB |
| testcase_07 | AC | 1 ms
6,820 KB |
| testcase_08 | AC | 1 ms
6,816 KB |
| testcase_09 | AC | 1 ms
6,820 KB |
| testcase_10 | AC | 1 ms
6,816 KB |
| testcase_11 | AC | 1 ms
6,816 KB |
| testcase_12 | AC | 1 ms
6,816 KB |
| testcase_13 | AC | 1 ms
6,816 KB |
| testcase_14 | AC | 1 ms
6,820 KB |
| testcase_15 | AC | 1 ms
6,816 KB |
| testcase_16 | AC | 1 ms
6,820 KB |
| testcase_17 | AC | 1 ms
6,816 KB |
| testcase_18 | AC | 1 ms
6,820 KB |
| testcase_19 | AC | 1 ms
6,820 KB |
| testcase_20 | AC | 1 ms
6,816 KB |
| testcase_21 | AC | 1 ms
6,820 KB |
| testcase_22 | AC | 1 ms
6,820 KB |
| testcase_23 | AC | 1 ms
6,816 KB |
| testcase_24 | AC | 1 ms
6,820 KB |
| testcase_25 | AC | 1 ms
6,816 KB |
| testcase_26 | AC | 1 ms
6,816 KB |
| testcase_27 | AC | 1 ms
6,820 KB |
| testcase_28 | AC | 1 ms
6,816 KB |
| testcase_29 | AC | 1 ms
6,820 KB |
| testcase_30 | AC | 1 ms
6,820 KB |
| testcase_31 | AC | 1 ms
6,820 KB |
| testcase_32 | AC | 1 ms
6,816 KB |
| testcase_33 | AC | 1 ms
6,820 KB |
| testcase_34 | AC | 1 ms
6,820 KB |
| testcase_35 | AC | 1 ms
6,820 KB |
| testcase_36 | AC | 1 ms
6,820 KB |
| testcase_37 | AC | 1 ms
6,816 KB |
| testcase_38 | AC | 1 ms
6,816 KB |
| testcase_39 | AC | 1 ms
6,820 KB |
| testcase_40 | AC | 1 ms
6,820 KB |
| testcase_41 | AC | 1 ms
6,816 KB |
| testcase_42 | AC | 1 ms
6,820 KB |
| testcase_43 | AC | 1 ms
6,816 KB |
| testcase_44 | AC | 1 ms
6,816 KB |
| testcase_45 | AC | 1 ms
6,820 KB |
| testcase_46 | AC | 1 ms
6,816 KB |
| testcase_47 | AC | 2 ms
6,816 KB |
| testcase_48 | AC | 1 ms
6,816 KB |
| testcase_49 | AC | 1 ms
6,816 KB |
| testcase_50 | AC | 1 ms
6,816 KB |
| testcase_51 | AC | 1 ms
6,816 KB |
| testcase_52 | AC | 1 ms
6,816 KB |
| testcase_53 | AC | 1 ms
6,816 KB |
ソースコード
pub use __cargo_equip::prelude::*;
use combination::Combination;
use fast_factorize::factor_count;
use formal_power_series::fps;
use modint::ModInt998244353 as Mint;
#[allow(unused_imports)]
use proconio::{
input,
marker::{Bytes, Chars, Usize1},
};
fn main() {
let comb = Combination::<Mint>::new();
let mut f = fps![0; 60];
for i in 1..=59 {
for j in 1..=59 / i {
f[i * j] += comb.inv(j);
}
}
let f = f.exp(60);
let f = f.iter().map(|&x| x.val() as usize).collect::<Vec<_>>();
input! {
n: usize,
}
let res = factor_count(n)
.iter()
.map(|&(_, x)| f[x])
.product::<usize>();
println!("{}", res);
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `algebraic 0.1.0 (path+████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebraic`
/// - `combination 0.1.0 (path+██████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::combination`
/// - `convolution-arbitrary-mod 0.1.0 (path+██████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::convolution_arbitrary_mod`
/// - `convolution-naive 0.1.0 (path+██████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::convolution_naive`
/// - `convolution-ntt-friendly 0.1.0 (path+█████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::convolution_ntt_friendly`
/// - `fast-factorize 0.1.0 (path+████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::fast_factorize`
/// - `formal-power-series 0.1.0 (path+███████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::formal_power_series`
/// - `modint 0.1.0 (path+█████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint`
/// - `montgomery-modint 0.1.0 (path+███████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::montgomery_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x:&Self::S)->Self::S;}pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar:ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip::crates::algebraic::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::algebraic::One for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);}
pub mod combination {use crate::__cargo_equip::preludes::combination::*;use std::cell::RefCell;use modint::ModInt;pub struct Combination<M:ModInt>{inv:RefCell<Vec<M>>,fact:RefCell<Vec<M>>,fact_inv:RefCell<Vec<M>>,}impl<M:ModInt>Combination<M>{pub fn new()->Self{Self{inv:RefCell::new(vec![M::from(0),M::from(1)]),fact:RefCell::new(vec![M::from(1);2]),fact_inv:RefCell::new(vec![M::from(1);2]),}}fn expand(&self,n:usize){let mut inv=self.inv.borrow_mut();let mut fact=self.fact.borrow_mut();let mut fact_inv=self.fact_inv.borrow_mut();let m=inv.len();let mut nn=m;while nn<=n{nn*=2;}inv.resize(nn,M::default());fact.resize(nn,M::default());fact_inv.resize(nn,M::default());let p=M::modulus()as usize;for i in m..nn{inv[i]=-inv[p%i]*M::from((p/i)as u32);fact[i]=fact[i-1]*M::from(i);fact_inv[i]=fact_inv[i-1]*inv[i];}}pub fn inv(&self,n:usize)->M{self.expand(n);self.inv.borrow()[n]}pub fn fact(&self,n:usize)->M{self.expand(n);self.fact.borrow()[n]}pub fn fact_inv(&self,n:usize)->M{self.expand(n);self.fact_inv.borrow()[n]}pub fn nck(&self,n:usize,k:usize)->M{if n<k{M::from(0)}else{self.expand(n);self.fact.borrow()[n]*self.fact_inv.borrow()[k]*self.fact_inv.borrow()[n-k]}}pub fn npk(&self,n:usize,k:usize)->M{if n<k{M::from(0)}else{self.expand(n);self.fact.borrow()[n]*self.fact_inv.borrow()[n-k]}}pub fn nhk(&self,n:usize,k:usize)->M{if n==0&&k==0{M::from(1)}else{self.nck(n+k-1,k)}}pub fn catalan(&self,n:usize)->M{self.expand(n*2);self.fact.borrow()[n*2]*self.fact_inv.borrow()[n+1]*self.fact_inv.borrow()[n]}}}
pub mod convolution_arbitrary_mod {use crate::__cargo_equip::preludes::convolution_arbitrary_mod::*;use convolution_naive::convolution_naive;use convolution_ntt_friendly::convolution_ntt_friendly;use modint::{ModInt,StaticModInt};const M1:u32=167_772_161;const M2:u32=469_762_049;const M3:u32=754_974_721;type Fp1=StaticModInt<M1>;type Fp2=StaticModInt<M2>;type Fp3=StaticModInt<M3>;pub fn convolution_arbitrary_mod<T:ModInt>(a:&[T],b:&[T])->Vec<T>{if a.len().min(b.len())<60{return convolution_naive(a,b);}let a1=a.iter().map(|&x|Fp1::new(x.val())).collect::<Vec<_>>();let a2=a.iter().map(|&x|Fp2::new(x.val())).collect::<Vec<_>>();let a3=a.iter().map(|&x|Fp3::new(x.val())).collect::<Vec<_>>();let b1=b.iter().map(|&x|Fp1::new(x.val())).collect::<Vec<_>>();let b2=b.iter().map(|&x|Fp2::new(x.val())).collect::<Vec<_>>();let b3=b.iter().map(|&x|Fp3::new(x.val())).collect::<Vec<_>>();let a1=convolution_ntt_friendly(a1,b1);let a2=convolution_ntt_friendly(a2,b2);let a3=convolution_ntt_friendly(a3,b3);a1.iter().zip(a2.iter()).zip(a3.iter()).map(|((&e1,&e2),&e3)|{let x1=e1;let x2=(e2-Fp2::new(x1.val()))*Fp2::new(Fp1::modulus()).inv();let x3=((e3-Fp3::new(x1.val()))*Fp3::new(Fp1::modulus()).inv()-Fp3::new(x2.val()))*Fp3::new(Fp2::modulus()).inv();T::from(x1.val())+T::from(x2.val())*T::from(Fp1::modulus())+T::from(x3.val())*T::from(Fp1::modulus())*T::from(Fp2::modulus())}).collect()}}
pub mod convolution_naive {use crate::__cargo_equip::preludes::convolution_naive::*;use modint::ModInt;pub fn convolution_naive<T:ModInt>(a:&[T],b:&[T])->Vec<T>{let n=a.len();let m=b.len();if n==0||m==0{return vec![];}let l=n+m-1;let mut c=vec![0.into();l];for i in 0..n{for j in 0..m{c[i+j]+=a[i]*b[j];}}c}}
pub mod convolution_ntt_friendly {use crate::__cargo_equip::preludes::convolution_ntt_friendly::*;use convolution_naive::convolution_naive;use modint::StaticModInt;pub fn ntt<const P:u32>(a:&mut[StaticModInt<P>]){assert!(StaticModInt::<P>::IS_NTT_FRIENDLY);let n=a.len();assert_eq!(n.count_ones(),1);let h=n.trailing_zeros()as usize;let mut len=0;while len<h{if h-len==1{let p=1<<h-len-1;let mut rot=StaticModInt::raw(1);for s in 0..1<<len{let offset=s<<h-len;for i in 0..p{let l=a[i+offset];let r=a[i+offset+p]*rot;a[i+offset]=l+r;a[i+offset+p]=l-r;}if s+1!=1<<len{rot*=StaticModInt::raw(StaticModInt::<P>::RATE2[(!s).trailing_zeros()as usize]);}}len+=1;}else{let p=1<<h-len-2;let mut rot=StaticModInt::<P>::raw(1);let imag=StaticModInt::<P>::raw(StaticModInt::<P>::ROOT[2]);for s in 0..1<<len{let rot2=rot*rot;let rot3=rot2*rot;let offset=s<<h-len;for i in 0..p{let mod2=(StaticModInt::<P>::modulus()as u64).pow(2);let a0=a[i+offset].val()as u64;let a1=a[i+offset+p].val()as u64*rot.val()as u64;let a2=a[i+offset+p*2].val()as u64*rot2.val()as u64;let a3=a[i+offset+p*3].val()as u64*rot3.val()as u64;let a1na3imag=StaticModInt::<P>::from(a1+mod2-a3).val()as u64*imag.val()as u64;let na2=mod2-a2;a[i+offset]=StaticModInt::from(a0+a2+a1+a3);a[i+offset+p]=StaticModInt::from(a0+a2+(mod2*2-(a1+a3)));a[i+offset+p*2]=StaticModInt::from(a0+na2+a1na3imag);a[i+offset+p*3]=StaticModInt::from(a0+na2+mod2-a1na3imag);}if s+1!=1<<len{rot*=StaticModInt::raw(StaticModInt::<P>::RATE3[(!s).trailing_zeros()as usize]);}}len+=2;}}}pub fn ntt_inv<const P:u32>(a:&mut[StaticModInt<P>]){assert!(StaticModInt::<P>::IS_NTT_FRIENDLY);let n=a.len();assert_eq!(n.count_ones(),1);let h=n.trailing_zeros()as usize;let mut len=h;while len>0{if len==1{let p=1<<h-len;let mut irot=StaticModInt::<P>::raw(1);for s in 0..1<<len-1{let offset=s<<h-len+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::<P>::from((StaticModInt::<P>::modulus()+l.val()-r.val())as u64*irot.val()as u64,);}if s+1!=1<<len-1{irot*=StaticModInt::<P>::raw(StaticModInt::<P>::IRATE2[(!s).trailing_zeros()as usize],);}}len-=1;}else{let p=1<<h-len;let mut irot=StaticModInt::<P>::raw(1);let iimag=StaticModInt::<P>::raw(StaticModInt::<P>::IROOT[2]);for s in 0..1<<len-2{let irot2=irot*irot;let irot3=irot2*irot;let offset=s<<h-len+2;for i in 0..p{let a0=a[i+offset].val()as u64;let a1=a[i+offset+p].val()as u64;let a2=a[i+offset+p*2].val()as u64;let a3=a[i+offset+p*3].val()as u64;let a2na3iimag=StaticModInt::<P>::from((StaticModInt::<P>::modulus()as u64+a2-a3)*iimag.val()as u64,).val()as u64;a[i+offset]=StaticModInt::<P>::from(a0+a1+a2+a3);a[i+offset+p]=StaticModInt::<P>::from((a0+(StaticModInt::<P>::modulus()as u64-a1)+a2na3iimag)*irot.val()as u64,);a[i+offset+p*2]=StaticModInt::<P>::from((a0+a1+(StaticModInt::<P>::modulus()as u64-a2)+(StaticModInt::<P>::modulus()as u64-a3))*irot2.val()as u64,);a[i+offset+p*3]=StaticModInt::<P>::from((a0+(StaticModInt::<P>::modulus()as u64-a1)+(StaticModInt::<P>::modulus()as u64-a2na3iimag))*irot3.val()as u64,);}if s+1!=1<<len-2{irot*=StaticModInt::<P>::raw(StaticModInt::<P>::IRATE3[(!s).trailing_zeros()as usize],);}}len-=2;}}let inv_n=StaticModInt::<P>::new(n).inv();for x in a.iter_mut(){*x*=inv_n;}}pub fn ntt_doubling<const P:u32>(a:&mut Vec<StaticModInt<P>>){let n=a.len();a.append(&mut a.clone());ntt_inv(&mut a[n..]);let mut r=StaticModInt::new(1);let zeta=StaticModInt::new(StaticModInt::<P>::G).pow((P-1)as usize/(n<<1));for i in n..n*2{a[i]*=r;r*=zeta;}ntt(&mut a[n..]);}pub fn convolution_ntt_friendly<const P:u32>(mut a:Vec<StaticModInt<P>>,mut b:Vec<StaticModInt<P>>,)->Vec<StaticModInt<P>>{let n=a.len();let m=b.len();if n==0||m==0{return vec![];}if n.min(m)<=60{return convolution_naive(&a,&b);}let len=n+m-1;let z=1<<64-(len-1).leading_zeros();a.resize(z,0.into());b.resize(z,0.into());ntt(&mut a);ntt(&mut b);for i in 0..z{a[i]*=b[i];}ntt_inv(&mut a);a.truncate(len);a}}
pub mod fast_factorize {use crate::__cargo_equip::preludes::fast_factorize::*;use std::{convert::{TryFrom,TryInto},fmt::Debug,mem::swap,};use montgomery_modint::MontgomeryModInt;pub fn is_prime(n:impl TryInto<u64,Error=impl Debug>)->bool{let n:u64=n.try_into().unwrap();if n&1==0{n==2}else if n<=1{false}else if n<1<<30{miller_rabin(n,&[2,7,61])}else{miller_rabin(n,&[2,325,9375,28178,450775,9780504,1795265022])}}pub fn factorize<N,E,F>(n:N)->Vec<N>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let n=n.try_into().unwrap();let mut f=factorize_(n);f.sort();f.into_iter().map(|x|x.try_into().unwrap()).collect()}pub fn factor_count<N,E,F>(n:N)->Vec<(N,usize)>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let f=factorize(n);if f.len()==0{return vec![];}let mut r=vec![(f[0],0)];for p in f{if r.last().unwrap().0==p{r.last_mut().unwrap().1+=1;}else{r.push((p,1));}}r}pub fn divisors<N,E,F>(n:N)->Vec<N>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let n=n.try_into().unwrap();if n==0{return vec![];}let fc=factor_count(n);let mut r=vec![1];for(p,c)in fc{for i in 0..r.len(){let mut x=r[i];for _ in 0..c{x*=p;r.push(x);}}}r.sort();r.into_iter().map(|x|x.try_into().unwrap()).collect()}fn gcd(mut a:u64,mut b:u64)->u64{while b!=0{a%=b;swap(&mut a,&mut b);}a}fn miller_rabin(n:u64,a:&[u64])->bool{MontgomeryModInt::set_modulus(n);let d=(n-1)>>(n-1).trailing_zeros();let e=MontgomeryModInt::new(1);let r=MontgomeryModInt::new(n-1);for&a in a{if n<=a{break;}let mut t=d;let mut y=MontgomeryModInt::new(a).pow(t);while t!=n-1&&y!=e&&y!=r{y*=y;t*=2;}if y!=r&&t%2==0{return false;}}true}fn pollard_rho(n:u64)->u64{if n&1==0{return 2;}else if is_prime(n){return n;}let m=1<<(64-n.leading_zeros())/8;let o=MontgomeryModInt::new(1);let mut c=o;loop{let f=|x:MontgomeryModInt|x*x+c;let mut x=o;let mut y=MontgomeryModInt::new(2);let mut ys=o;let mut q=o;let mut r=1;let mut g=1;while g==1{x=y;for _ in 0..r{y=f(y);}for k in(0..r).step_by(m){if g!=1{break;}ys=y;for _ in 0..m.min(r-k){y=f(y);q*=x-y;}g=gcd(q.val(),n);}r<<=1;}if g==n{g=1;while g==1{ys=f(ys);g=gcd((x-ys).val(),n);}}if g<n{return if is_prime(g){g}else if is_prime(n/g){n/g}else{pollard_rho(g)};}c+=o;}}fn factorize_(n:u64)->Vec<u64>{if n<=1{return vec![];};let p=pollard_rho(n);if p==n{return vec![p];}let mut r=factorize_(p);r.extend(factorize_(n/p));r}}
pub mod formal_power_series {use crate::__cargo_equip::preludes::formal_power_series::*;pub use crate::__cargo_equip::macros::formal_power_series::*;use convolution_arbitrary_mod::convolution_arbitrary_mod;use convolution_ntt_friendly::{convolution_ntt_friendly,ntt,ntt_inv};use modint::StaticModInt;use std::{fmt::{Debug,Display},iter::repeat,mem::swap,ops::{Add,AddAssign,Deref,DerefMut,Div,DivAssign,Mul,MulAssign,Neg,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};#[derive(Default,Clone,PartialEq,Eq)]#[repr(transparent)]pub struct FormalPowerSeries<const P:u32>(pub Vec<StaticModInt<P>>);pub type FormalPowerSeries998244353=FormalPowerSeries<998_244_353>;pub type FormalPowerSeries1000000007=FormalPowerSeries<1_000_000_007>;#[macro_export]macro_rules!__cargo_equip_macro_def_formal_power_series_fps{($($x:expr),*)=>($crate::__cargo_equip::crates::formal_power_series::FormalPowerSeries(vec![$(modint::StaticModInt::from($x)),*]));($x:expr;$n:expr)=>($crate::__cargo_equip::crates::formal_power_series::FormalPowerSeries(vec![modint::StaticModInt::from($x);$n]));}macro_rules!fps{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_formal_power_series_fps!{$($tt)*})}impl<const P:u32>FormalPowerSeries<P>{pub fn shrink(&mut self){while self.last()==Some(&0.into()){self.pop();}}pub fn pre(&self,d:usize)->Self{Self(self.0[0..d.min(self.len())].to_vec())}pub fn eval(&self,x:StaticModInt<P>)->StaticModInt<P>{let mut r=0.into();let mut w=StaticModInt::new(1);for&v in&self.0{r+=w*v;w*=x;}r}pub fn count_terms(&self)->usize{self.iter().filter(|&&v|v.val()!=0).count()}pub fn differential(&self)->Self{Self(self.iter().enumerate().skip(1).map(|(i,v)|v*i).collect(),)}pub fn integral(&self)->Self{let n=self.len();let mut res=fps![0;n+1];if n>0{res[1]=1.into();}let m=StaticModInt::<P>::modulus()as usize;for i in 2..=n{res[i]=-res[m%i]*(m/i);}for i in 0..n{res[i+1]*=self[i];}res}pub fn div_mod(&self,g:&Self)->(Self,Self){assert!(g.last().unwrap().val()!=0);if self.len()<g.len(){return(fps![],self.clone());}let mut rf=self.clone();let mut rg=g.clone();rf.reverse();rg.reverse();let n=rf.len()-rg.len()+1;rf.resize(n,0.into());rg.resize(n,0.into());let mut q=rf*rg.inv(n);q.resize(n,0.into());q.reverse();let h=&q*g;let mut f=self.clone();for i in 0..f.len(){f[i]-=h[i];}f.shrink();(q,f)}pub fn inv(&self,d:usize)->Self{assert_ne!(self[0].val(),0);if StaticModInt::<P>::IS_NTT_FRIENDLY{let mut res=fps![0;d];res[0]=self[0].inv();for k in 0..{let k=1<<k;if k>=d{break;}let mut f=Self(self.iter().take(k*2).map(|&x|x).collect());f.resize(k*2,0.into());let mut g=Self(res.iter().take(k).map(|&x|x).collect());g.resize(k*2,0.into());ntt(&mut f);ntt(&mut g);for(a,b)in f.iter_mut().zip(g.iter()){*a*=b;}ntt_inv(&mut f);for a in f.iter_mut().take(k){*a=0.into();}ntt(&mut f);for(a,b)in f.iter_mut().zip(g.iter()){*a*=b;}ntt_inv(&mut f);for(a,b)in res.iter_mut().zip(f.iter()).skip(k){*a=-b;}}res.truncate(d);res}else{let mut res=fps![self[0].inv()];for k in 0..{let k=1<<k;if k>=d{break;}res=(&res+&res-&res*&res*self.pre(k*2)).pre(k*2);}res.truncate(d);res}}pub fn log(&self,d:usize)->Self{assert!(self[0].val()==1);(self.differential()*self.inv(d)).pre(d-1).integral()}pub fn exp(&self,d:usize)->Self{assert!(self.len()==0||self[0].val()==0);if StaticModInt::<P>::IS_NTT_FRIENDLY{let mut b=fps![1,if self.len()>1{self[1]}else{0.into()}];let mut c=fps![1];let mut z1;let mut z2=fps![1,1];for m in 1..{let m=1<<m;if m>=d{break;}let mut y=b.clone();y.resize(m*2,0.into());ntt(&mut y);z1=z2;let mut z=Self((0..m).map(|i|y[i]*z1[i]).collect());ntt_inv(&mut z);for v in z.iter_mut().take(m/2){*v=0.into();}ntt(&mut z);for i in 0..m{z[i]*=-z1[i];}ntt_inv(&mut z);c.append(&mut z.drain(m/2..).collect());z2=c.clone();z2.resize(m*2,0.into());ntt(&mut z2);let mut x:Self=self.clone().pre(m);x.resize(m,0.into());x=x.differential();x.push(0.into());ntt(&mut x);for i in 0..m{x[i]*=y[i];}ntt_inv(&mut x);x-=b.differential();x.resize(m*2,0.into());for i in 0..m-1{x[m+i]=x[i];x[i]=0.into();}ntt(&mut x);for i in 0..m*2{x[i]*=z2[i];}ntt_inv(&mut x);x.pop();x=x.integral();for i in m..self.len().min(m*2){x[i]+=self[i];}for v in x.iter_mut().take(m){*v=0.into();}ntt(&mut x);for i in 0..m*2{x[i]*=y[i];}ntt_inv(&mut x);b.append(&mut x.drain(m..).collect());}b.pre(d)}else{let mut res=fps![1];for i in 0..{let i=1<<i;if i>=d{break;}let mut t=self.clone().pre(i<<1);t[0]+=1;t-=res.log(i<<1);res=(res*t).pre(i<<1);}res.pre(d)}}pub fn pow(&self,k:usize,d:usize)->FormalPowerSeries<P>{let n=self.len();if k==0{let mut res=fps![0;d];if d>0{res[0]=1.into();}return res;}for i in 0..n{if self[i].val()!=0{let c=self[i].inv();let mut res=(((self*c)>>i).log(d)*StaticModInt::new(k)).exp(d);res*=self[i].pow(k);res=(res<<i*k).pre(d);if res.len()<d{res.resize(d,0.into());}return res;}if(i+1).saturating_mul(k)>=d{return fps![0;d];}}fps![0;d]}pub fn sqrt(&self,d:usize)->Option<FormalPowerSeries<P>>{if self.len()==0{return Some(fps![0;d]);}if self[0].val()==0{if let Some(i)=self.iter().position(|&x|x.val()!=0){if i&1!=0{return None;}else if d<=i/2{return Some(fps![0;d]);}let mut res=(self>>i).sqrt(d-i/2)?;res<<=i/2;if res.len()<d{res.resize(d,0.into());}return Some(res);}return Some(fps![0;d]);}let r=self[0].sqrt()?;assert_eq!(r*r,self[0]);let mut res=fps![r];let inv2=StaticModInt::new(2).inv();for i in 0..{let i=1<<i;if i>=d{break;}res=(&res+self.clone().pre(i<<1)*res.inv(i<<1))*inv2;}Some(res.pre(d))}pub fn multipoint_evaluate(&self,xs:&[StaticModInt<P>])->Vec<StaticModInt<P>>{let m=xs.len();if m==0{return vec![];}let m2=1<<64-(m-1).leading_zeros();let mut g=vec![fps![1];m2+m2];for i in 0..m{g[m2+i]=fps![-xs[i],1];}for i in(1..m2).rev(){g[i]=&g[i<<1|0]*&g[i<<1|1];}g[1]=self.div_mod(&g[1]).1;for i in 2..m2+m{g[i]=g[i>>1].div_mod(&g[i]).1;}(m2..m2+m).map(|i|if g[i].len()==0{0.into()}else{g[i][0]}).collect()}pub fn taylor_shift(mut self,c:StaticModInt<P>)->Self{if self.len()==0{return self;}let n=self.len();let mut fact=vec![StaticModInt::new(1);n];let mut inv=vec![StaticModInt::new(1);n];let mut fact_inv=vec![StaticModInt::new(1);n];for i in 1..n{fact[i]=fact[i-1]*i;}fact_inv[n-1]=fact[n-1].inv();for i in(1..n).rev(){inv[i]=fact_inv[i]*fact[i-1];fact_inv[i-1]=fact_inv[i]*i;}for i in 0..n{self[i]*=fact[i];}self.reverse();let mut g=fps![1;n];for i in 1..n{g[i]=g[i-1]*c*inv[i];}self=(self*g).pre(n);self.reverse();for i in 0..n{self[i]*=fact_inv[i];}self}}impl<const P:u32>Debug for FormalPowerSeries<P>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{:?}",&self.0))}}impl<const P:u32>Display for FormalPowerSeries<P>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{if self.len()!=0{f.write_fmt(format_args!("{}",self[0]))?;}for v in self.iter().skip(1){f.write_fmt(format_args!(" {}",v))?;}Ok(())}}impl<const P:u32>Deref for FormalPowerSeries<P>{type Target=Vec<StaticModInt<P>>;fn deref(&self)->&Self::Target{&self.0}}impl<const P:u32>DerefMut for FormalPowerSeries<P>{fn deref_mut(&mut self)->&mut Self::Target{&mut self.0}}impl<const P:u32>From<Vec<StaticModInt<P>>>for FormalPowerSeries<P>{fn from(v:Vec<StaticModInt<P>>)->Self{Self(v)}}impl<const P:u32>Neg for FormalPowerSeries<P>{type Output=Self;fn neg(mut self)->Self::Output{for v in self.iter_mut(){*v=-*v;}self}}impl<const P:u32>Neg for&FormalPowerSeries<P>{type Output=FormalPowerSeries<P>;fn neg(self)->Self::Output{-self.clone()}}impl<const P:u32>MulAssign<StaticModInt<P>>for FormalPowerSeries<P>{fn mul_assign(&mut self,rhs:StaticModInt<P>){for v in self.iter_mut(){*v*=rhs;}}}impl<const P:u32>DivAssign<StaticModInt<P>>for FormalPowerSeries<P>{fn div_assign(&mut self,rhs:StaticModInt<P>){*self*=rhs.inv();}}impl<const P:u32>AddAssign<Self>for FormalPowerSeries<P>{fn add_assign(&mut self,rhs:Self){if self.len()<rhs.len(){self.resize(rhs.len(),0.into());}self.iter_mut().zip(rhs.iter()).for_each(|(a,b)|*a+=b);}}impl<const P:u32>SubAssign<Self>for FormalPowerSeries<P>{fn sub_assign(&mut self,rhs:Self){if self.len()<rhs.len(){self.resize(rhs.len(),0.into());}self.iter_mut().zip(rhs.iter()).for_each(|(a,b)|*a-=b);}}impl<const P:u32>MulAssign<Self>for FormalPowerSeries<P>{fn mul_assign(&mut self,rhs:Self){if rhs.len()==0{*self=fps![];return;}if rhs.count_terms()<64{let mut v=vec![];for i in 0..rhs.len(){if i==0||rhs[i].val()!=0{v.push((i,rhs[i]));}}let n=self.len();self.resize(n+rhs.len()-1,0.into());for i in(0..n).rev(){for&(j,c)in v.iter().rev(){if j>0{self[i+j]=self[i+j]+self[i]*c;}else{self[i]*=c;}}}}else if StaticModInt::<P>::IS_NTT_FRIENDLY{let mut a=vec![];swap(&mut a,&mut self.0);self.0=convolution_ntt_friendly(a,rhs.0);}else{self.0=convolution_arbitrary_mod(&self.0,&rhs.0);}}}impl<const P:u32>DivAssign<Self>for FormalPowerSeries<P>{fn div_assign(&mut self,mut g:Self){if g.count_terms()<64{if g[0].val()!=1{let c=g[0].inv();for v in self.iter_mut(){*v*=c;}for v in g.iter_mut(){*v*=c;}}let mut v=vec![];for i in 1..g.len(){if g[i].val()!=0{v.push((i,-g[i]));}}for i in 0..self.len(){for&(j,c)in&v{if i>=j{self[i]=self[i]+self[i-j]*c;}}}}else{let n=self.len();*self*=g.inv(n);self.truncate(n);}}}impl<const P:u32>ShlAssign<usize>for FormalPowerSeries<P>{fn shl_assign(&mut self,rhs:usize){self.0=repeat(0.into()).take(rhs).chain(self.0.drain(..)).collect();}}impl<const P:u32>ShrAssign<usize>for FormalPowerSeries<P>{fn shr_assign(&mut self,rhs:usize){self.0=self.0.drain(rhs..).collect();}}macro_rules!impl_ops{($($ty_l:ty,$ty_r:ty,$trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl<const P:u32>$trait_assign<&$ty_r>for$ty_l{fn$fn_assign(&mut self,rhs:&$ty_r){self.$fn_assign(rhs.clone());}}impl<const P:u32>$trait<$ty_r>for$ty_l{type Output=$ty_l;fn$fn(mut self,rhs:$ty_r)->$ty_l{self.$fn_assign(rhs);self}}impl<const P:u32>$trait<$ty_r>for&$ty_l{type Output=$ty_l;fn$fn(self,rhs:$ty_r)->$ty_l{let mut r=self.clone();r.$fn_assign(rhs);r}}impl<const P:u32>$trait<&$ty_r>for$ty_l{type Output=$ty_l;fn$fn(mut self,rhs:&$ty_r)->$ty_l{self.$fn_assign(rhs.clone());self}}impl<const P:u32>$trait<&$ty_r>for&$ty_l{type Output=$ty_l;fn$fn(self,rhs:&$ty_r)->$ty_l{let mut r=self.clone();r.$fn_assign(rhs.clone());r}})*};}impl_ops!{FormalPowerSeries<P>,StaticModInt<P>,Mul,MulAssign,mul,mul_assign,FormalPowerSeries<P>,StaticModInt<P>,Div,DivAssign,div,div_assign,FormalPowerSeries<P>,FormalPowerSeries<P>,Add,AddAssign,add,add_assign,FormalPowerSeries<P>,FormalPowerSeries<P>,Sub,SubAssign,sub,sub_assign,FormalPowerSeries<P>,FormalPowerSeries<P>,Mul,MulAssign,mul,mul_assign,FormalPowerSeries<P>,FormalPowerSeries<P>,Div,DivAssign,div,div_assign,FormalPowerSeries<P>,usize,Shl,ShlAssign,shl,shl_assign,FormalPowerSeries<P>,usize,Shr,ShrAssign,shr,shr_assign,}}
pub mod modint {use crate::__cargo_equip::preludes::modint::*;use std::{fmt,hash::Hash,iter::{Product,Sum},num::ParseIntError,ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},str::FromStr,sync::atomic::{self,AtomicU32,AtomicU64},};use algebraic::{One,Zero};#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct StaticModInt<const P:u32>(u32);#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct DynamicModInt(u32);pub type ModInt998244353=StaticModInt<998_244_353>;pub type ModInt1000000007=StaticModInt<1_000_000_007>;pub trait ModInt:Default+Zero+One+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;fn pow(self,k:usize)->Self;fn sqrt(self)->Option<Self>;}const fn mul(x:u32,y:u32,m:u32)->u32{(x as u64*y as u64%m as u64)as u32}const fn pow(x:u32,mut n:u32,m:u32)->u32{if m==1{return 0;}let mut r=1u64;let mut y=(x%m)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 u32}const fn is_prime(n:u32)->bool{match n{_ if n<=1=>return false,2|7|61=>return true,_ if n&1==0=>return false,_=>{}}let mut d=n-1;while d&1==0{d>>=1;}let a=[2,7,61];let mut i=0;while i<3{let mut t=d;let mut y=pow(a[i],t,n);while t!=n-1&&y!=1&&y!=n-1{y=(y as u64*y as u64%n as u64)as u32;t<<=1;}if y!=n-1&&t&1==0{return false;}i+=1;}true}const fn extgcd(mut a:u32,b:u32)->(u32,u32){a=a%b;if a==0{return(b,0);}let mut s=b as i64;let mut t=a as i64;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;let tmp=s;s=t;t=tmp;let tmp=m0;m0=m1;m1=tmp;}if m0<0{m0+=b as i64/s;}(s as u32,m0 as u32)}const fn primitive_root(m:u32)->u32{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;}let mut i=3;while i<std::u32::MAX{if i as u64*i as u64>x as u64{break;}if x%i==0{divs[cnt]=i;cnt+=1;while x%i==0{x/=i;}}i+=2;}if x>1{divs[cnt]=x;cnt+=1;}let mut g=2;loop{let mut i=0;while i<cnt{if pow(g,(m-1)/divs[i],m)==1{break;}i+=1;}if i==cnt{break g;}g+=1;}}const fn ntt_info(m:u32,)->(u32,usize,[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],){let g=primitive_root(m);let rank2=(m-1).trailing_zeros()as usize;let mut root=[0;30];let mut iroot=[0;30];let mut rate2=[0;30];let mut irate2=[0;30];let mut rate3=[0;30];let mut irate3=[0;30];root[rank2]=pow(g,(m-1)>>rank2,m);iroot[rank2]=extgcd(root[rank2],m).1;let mut i=rank2;while i>0{i-=1;root[i]=mul(root[i+1],root[i+1],m);iroot[i]=mul(iroot[i+1],iroot[i+1],m);}let mut prod=1;let mut iprod=1;let mut i=0;while i+2<=rank2{rate2[i]=mul(root[i+2],prod,m);irate2[i]=mul(iroot[i+2],iprod,m);prod=mul(prod,iroot[i+2],m);iprod=mul(iprod,root[i+2],m);i+=1;}let mut prod=1;let mut iprod=1;let mut i=0;while i+3<=rank2{rate3[i]=mul(root[i+3],prod,m);irate3[i]=mul(iroot[i+3],iprod,m);prod=mul(prod,iroot[i+3],m);iprod=mul(iprod,root[i+3],m);i+=1;}(g,rank2,root,iroot,rate2,irate2,rate3,irate3)}fn rat_convert(x:u64,m:u64,d:u64)->Option<(u64,u64)>{let n=m/(2*d);if x<n&&1<d{return Some((x,1));}let mut l=(0,1);let mut r=(1,0);loop{let num=l.0+r.0;let den=l.1+r.1;let(i,q)=match(num*m).cmp(&(den*x)){std::cmp::Ordering::Less=>{let k=(x*l.1-m*l.0-1)/(m*r.0-x*r.1);l.0+=k*r.0;l.1+=k*r.1;l}std::cmp::Ordering::Equal=>return None,std::cmp::Ordering::Greater=>{let k=(m*r.0-x*r.1-1)/(x*l.1-m*l.0);r.0+=k*l.0;r.1+=k*l.1;r}};if q*x<i*m{continue;}let p=q*x-i*m;if p<n&&q<d{return Some((p,q));}}}impl<const P:u32>ModInt for StaticModInt<P>{#[inline(always)]fn modulus()->u32{P}#[inline]fn raw(val:u32)->Self{Self(val)}#[inline]fn val(self)->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k)}fn sqrt(self)->Option<Self>{self.sqrt()}}impl<const P:u32>StaticModInt<P>{#[inline]pub fn new<T:Into<StaticModInt<P>>>(x:T)->Self{x.into()}#[inline(always)]pub fn modulus()->u32{P}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self.0}#[inline]pub fn inv(self)->Self{assert_ne!(self.0,0);self.pow(P as usize-2)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::from(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val()<2{return Some(self);}else if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b+=1;}let mut e=(p-1).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m);while y.val()!=1{let mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}}impl ModInt for DynamicModInt{#[inline(always)]fn modulus()->u32{BARRETT.modulus()}#[inline]fn raw(val:u32)->Self{Self(val)}#[inline]fn val(self)->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k)}fn sqrt(self)->Option<Self>{self.sqrt()}}impl DynamicModInt{#[inline]pub fn new<T:Into<DynamicModInt>>(x:T)->Self{x.into()}#[inline(always)]pub fn modulus()->u32{BARRETT.modulus()}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self.0}#[inline]pub fn inv(self)->Self{let(g,x)=extgcd(self.0,Self::modulus());assert_eq!(g,1);Self(x)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::from(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val()<2{return Some(self);}else if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b+=1;}let mut e=(p-1).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m);while y.val()!=1{let mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}pub fn set_modulus(modulus:u32){BARRETT.set(modulus)}}struct Barrett{m:AtomicU32,im:AtomicU64,}impl Barrett{const fn new(m:u32)->Self{Self{m:AtomicU32::new(m),im:AtomicU64::new((!0/m as u64).wrapping_add(1)),}}#[inline]fn set(&self,m:u32){let im=(!0/m as u64).wrapping_add(1);self.m.store(m,atomic::Ordering::SeqCst);self.im.store(im,atomic::Ordering::SeqCst);}#[inline]fn modulus(&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);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}}static BARRETT:Barrett=Barrett::new(998_244_353);impl<const P:u32>FromStr for StaticModInt<P>{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl FromStr for DynamicModInt{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl<const P:u32>fmt::Display for StaticModInt<P>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}impl fmt::Display for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}impl<const P:u32>fmt::Debug for StaticModInt<P>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{if let Some((num,den))=rat_convert(self.0 as u64,P as u64,1025){write!(f,"{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else if let Some((num,den))=rat_convert((P-self.0)as u64,P as u64,1025){write!(f,"-{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else{write!(f,"{}",self.0)?;}Ok(())}}impl fmt::Debug for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}macro_rules!impl_from_integer{($(($t1:ty,$t2:ty)),*)=>{$(impl<const P:u32>From<$t1>for StaticModInt<P>{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(P as$t2)as u32)}}impl From<$t1>for DynamicModInt{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(Self::modulus()as$t2)as u32)}})*};}impl_from_integer!((i8,i32),(i16,i32),(i32,i32),(i64,i64),(isize,i64),(i128,i128),(u8,u32),(u16,u32),(u32,u32),(u64,u64),(usize,u64),(u128,u128));impl<const P:u32,T:Into<Self>>AddAssign<T>for StaticModInt<P>{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=P{self.0-=P;}}}impl<T:Into<Self>>AddAssign<T>for DynamicModInt{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=Self::modulus(){self.0-=Self::modulus();}}}impl<const P:u32,T:Into<Self>>SubAssign<T>for StaticModInt<P>{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=P;}self.0-=rhs;}}impl<T:Into<Self>>SubAssign<T>for DynamicModInt{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=Self::modulus();}self.0-=rhs;}}impl<const P:u32,T:Into<Self>>MulAssign<T>for StaticModInt<P>{fn mul_assign(&mut self,rhs:T){*self=Self((self.0 as u64*rhs.into().0 as u64%P as u64)as u32);}}impl<T:Into<Self>>MulAssign<T>for DynamicModInt{fn mul_assign(&mut self,rhs:T){*self=Self(BARRETT.mul(self.0,rhs.into().0));}}impl<const P:u32,T:Into<Self>>DivAssign<T>for StaticModInt<P>{fn div_assign(&mut self,rhs:T){*self*=rhs.into().inv()}}impl<T:Into<Self>>DivAssign<T>for DynamicModInt{fn div_assign(&mut self,rhs:T){*self=*self*rhs.into().inv()}}impl<const P:u32>Neg for StaticModInt<P>{type Output=Self;fn neg(self)->Self::Output{if self.0==0{Self(0)}else{Self(P-self.0)}}}impl Neg for DynamicModInt{type Output=Self;fn neg(self)->Self::Output{if self.0==0{Self(0)}else{Self(Self::modulus()-self.0)}}}impl<const P:u32>Neg for&StaticModInt<P>{type Output=StaticModInt<P>;fn neg(self)->Self::Output{if self.0==0{StaticModInt(0)}else{StaticModInt(P-self.0)}}}impl Neg for&DynamicModInt{type Output=DynamicModInt;fn neg(self)->Self::Output{if self.0==0{DynamicModInt(0)}else{DynamicModInt(DynamicModInt::modulus()-self.0)}}}macro_rules!impl_ops{($($trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl<const P:u32>$trait_assign<&StaticModInt<P>>for StaticModInt<P>{fn$fn_assign(&mut self,rhs:&StaticModInt<P>){self.$fn_assign(*rhs);}}impl<const P:u32,T:Into<StaticModInt<P>>>$trait<T>for StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl<const P:u32>$trait<&StaticModInt<P>>for StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P>)->Self::Output{self.$fn(*rhs)}}impl<const P:u32,T:Into<StaticModInt<P>>>$trait<T>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl<const P:u32>$trait<&StaticModInt<P>>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P>)->Self::Output{(*self).$fn(*rhs)}}impl$trait_assign<&DynamicModInt>for DynamicModInt{fn$fn_assign(&mut self,rhs:&DynamicModInt){self.$fn_assign(*rhs);}}impl<T:Into<DynamicModInt>>$trait<T>for DynamicModInt{type Output=DynamicModInt;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl$trait<&DynamicModInt>for DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:&DynamicModInt)->Self::Output{self.$fn(*rhs)}}impl<T:Into<DynamicModInt>>$trait<T>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl$trait<&DynamicModInt>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:&DynamicModInt)->Self::Output{(*self).$fn(*rhs)}})*};}impl_ops!{Add,AddAssign,add,add_assign,Sub,SubAssign,sub,sub_assign,Mul,MulAssign,mul,mul_assign,Div,DivAssign,div,div_assign,}impl<const P:u32>Sum for StaticModInt<P>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}impl<const P:u32>Product for StaticModInt<P>{fn product<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}impl<'a,const P:u32>Sum<&'a Self>for StaticModInt<P>{fn sum<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}impl<'a,const P:u32>Product<&'a Self>for StaticModInt<P>{fn product<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}impl<const P:u32>StaticModInt<P>{pub const G:u32=ntt_info(P).0;pub const RANK2:usize=ntt_info(P).1;pub const ROOT:[u32;30]=ntt_info(P).2;pub const IROOT:[u32;30]=ntt_info(P).3;pub const RATE2:[u32;30]=ntt_info(P).4;pub const IRATE2:[u32;30]=ntt_info(P).5;pub const RATE3:[u32;30]=ntt_info(P).6;pub const IRATE3:[u32;30]=ntt_info(P).7;pub const IS_NTT_FRIENDLY:bool=is_prime(P)&&Self::RANK2>=21;}impl<const P:u32>Zero for StaticModInt<P>{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl<const P:u32>One for StaticModInt<P>{fn one()->Self{Self::new(1)}fn is_one(&self)->bool{self==&Self::one()}}impl Zero for DynamicModInt{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl One for DynamicModInt{fn one()->Self{Self::new(1)}fn is_one(&self)->bool{self==&Self::one()}}}
pub mod montgomery_modint {use crate::__cargo_equip::preludes::montgomery_modint::*;use std::{convert::TryInto,fmt::Debug,ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign},sync::atomic::{AtomicU64,Ordering::SeqCst},};use algebraic::{One,Zero};struct Montgomery{m:AtomicU64,r:AtomicU64,n2:AtomicU64,}impl Montgomery{const fn new()->Self{Self{m:AtomicU64::new(0),r:AtomicU64::new(0),n2:AtomicU64::new(0),}}fn set(&self,m:u64){assert!(m<1<<62);assert!(m&1!=0);if self.m.load(SeqCst)==m{return;}let n2=((m as u128).wrapping_neg()%m as u128)as u64;let mut r=m;for _ in 0..5{r=r.wrapping_mul(2u64.wrapping_sub(m.wrapping_mul(r)));}assert!(r.wrapping_mul(m)==1);self.m.store(m,SeqCst);self.r.store(r,SeqCst);self.n2.store(n2,SeqCst);}fn reduce(&self,x:u128)->u64{let r=self.r.load(SeqCst);let m=self.m.load(SeqCst);(x.wrapping_add(((x as u64).wrapping_mul(r.wrapping_neg())as u128).wrapping_mul(m as u128),)>>64)as u64}}static MONTGOMERY:Montgomery=Montgomery::new();#[derive(Default,Clone,Copy)]pub struct MontgomeryModInt(u64);impl MontgomeryModInt{pub fn set_modulus(m:u64){MONTGOMERY.set(m);}pub fn modulus()->u64{MONTGOMERY.m.load(SeqCst)}pub fn new(x:u64)->Self{Self(MONTGOMERY.reduce((x as u128).wrapping_add(Self::modulus()as u128).wrapping_mul(MONTGOMERY.n2.load(SeqCst)as u128),),)}pub fn pow(mut self,k:impl TryInto<u128,Error=impl Debug>)->Self{let mut k:u128=k.try_into().unwrap();let mut r=Self::new(1);while k>0{if k&1!=0{r*=self;}self*=self;k>>=1;}r}pub fn val(self)->u64{let x=MONTGOMERY.reduce(self.0 as u128);let m=Self::modulus();if x>=m{x-m}else{x}}}impl Neg for MontgomeryModInt{type Output=Self;fn neg(self)->Self::Output{Self::new(0)-self}}impl AddAssign<Self>for MontgomeryModInt{fn add_assign(&mut self,rhs:Self){let m=Self::modulus();self.0=self.0.wrapping_add(rhs.0.wrapping_sub(m*2));if(self.0 as i64)<0{self.0=self.0.wrapping_add(m*2);}}}impl SubAssign<Self>for MontgomeryModInt{fn sub_assign(&mut self,rhs:Self){let m=Self::modulus();self.0=self.0.wrapping_sub(rhs.0);if(self.0 as i64)<0{self.0=self.0.wrapping_add(m*2);}}}impl MulAssign<Self>for MontgomeryModInt{fn mul_assign(&mut self,rhs:Self){self.0=MONTGOMERY.reduce(self.0 as u128*rhs.0 as u128);}}impl Add<Self>for MontgomeryModInt{type Output=Self;fn add(mut self,rhs:Self)->Self::Output{self+=rhs;self}}impl Sub<Self>for MontgomeryModInt{type Output=Self;fn sub(mut self,rhs:Self)->Self::Output{self-=rhs;self}}impl Mul<Self>for MontgomeryModInt{type Output=Self;fn mul(mut self,rhs:Self)->Self::Output{self*=rhs;self}}impl PartialEq for MontgomeryModInt{fn eq(&self,other:&Self)->bool{let m=Self::modulus();(if self.0>=m{self.0-m}else{self.0})==(if other.0>=m{other.0-m}else{other.0})}}impl Eq for MontgomeryModInt{}impl Zero for MontgomeryModInt{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl One for MontgomeryModInt{fn one()->Self{Self(1)}fn is_one(&self)->bool{self==&Self::new(1)}}}
}
pub(crate) mod macros {
pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};}
pub mod combination {}
pub mod convolution_arbitrary_mod {}
pub mod convolution_naive {}
pub mod convolution_ntt_friendly {}
pub mod fast_factorize {}
pub mod formal_power_series {pub use crate::__cargo_equip_macro_def_formal_power_series_fps as fps;}
pub mod modint {}
pub mod montgomery_modint {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod algebraic {}
pub mod combination {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::modint;}
pub mod convolution_arbitrary_mod {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{convolution_naive,convolution_ntt_friendly,modint};}
pub mod convolution_naive {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::modint;}
pub mod convolution_ntt_friendly {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{convolution_naive,modint};}
pub mod fast_factorize {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::montgomery_modint;}
pub mod formal_power_series {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{convolution_arbitrary_mod,convolution_ntt_friendly,modint};}
pub mod modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
pub mod montgomery_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
}
}