pub use __cargo_equip::prelude::*; use formal_power_series::{fps, FormalPowerSeries998244353 as FPS}; use mo::Mo; use modint::ModInt998244353 as Mint; #[allow(unused_imports)] use proconio::{ input, marker::{Bytes, Chars, Usize1}, }; fn main() { input! { n: usize, a: [Mint; n], q: usize, abk: [(Usize1, usize, usize); q], } let mut s: Vec = vec![fps![1]; n + 1]; for i in 0..n { s[i + 1] = &s[i] * fps![1, a[i]]; } for &(a, b, k) in &abk { println!("{}", (&s[b] / &s[a])[k]); } } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `convolution-arbitrary-mod 0.1.0 (path+██████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__convolution_arbitrary_mod_0_1_0` /// - `convolution-naive 0.1.0 (path+██████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__convolution_naive_0_1_0` /// - `convolution-ntt-friendly 0.1.0 (path+█████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::convolution_ntt_friendly` /// - `formal-power-series 0.1.0 (path+███████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::formal_power_series` /// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::__lazy_static_1_4_0` /// - `mo 0.1.0 (path+█████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::mo` /// - `modint 0.1.0 (path+█████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint` /// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio` /// /// # License and Copyright Notices /// /// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` /// /// ```text /// Copyright (c) 2010 The Rust Project Developers /// /// Permission is hereby granted, free of charge, to any /// person obtaining a copy of this software and associated /// documentation files (the "Software"), to deal in the /// Software without restriction, including without /// limitation the rights to use, copy, modify, merge, /// publish, distribute, sublicense, and/or sell copies of /// the Software, and to permit persons to whom the Software /// is furnished to do so, subject to the following /// conditions: /// /// The above copyright notice and this permission notice /// shall be included in all copies or substantial portions /// of the Software. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF /// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED /// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A /// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT /// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY /// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION /// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR /// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER /// DEALINGS IN THE SOFTWARE. /// ``` /// /// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` /// /// ```text /// The MIT License /// Copyright 2019 (C) statiolake /// /// Permission is hereby granted, free of charge, to any person obtaining a copy of /// this software and associated documentation files (the "Software"), to deal in /// the Software without restriction, including without limitation the rights to /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of /// the Software, and to permit persons to whom the Software is furnished to do so, /// subject to the following conditions: /// /// The above copyright notice and this permission notice shall be included in all /// copies or substantial portions of the Software. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS /// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR /// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER /// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN /// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. /// /// Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019. The /// original macro is licensed under BSD 3-clause license. /// /// Redistribution and use in source and binary forms, with or without /// modification, are permitted provided that the following conditions are met: /// /// 1. Redistributions of source code must retain the above copyright notice, this /// list of conditions and the following disclaimer. /// /// 2. Redistributions in binary form must reproduce the above copyright notice, /// this list of conditions and the following disclaimer in the documentation /// and/or other materials provided with the distribution. /// /// 3. Neither the name of the copyright holder nor the names of its contributors /// may be used to endorse or promote products derived from this software /// without specific prior written permission. /// /// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND /// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED /// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE /// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE /// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL /// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR /// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER /// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, /// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE /// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. /// ``` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod __convolution_arbitrary_mod_0_1_0 {use crate::__cargo_equip::preludes::__convolution_arbitrary_mod_0_1_0::*;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;type Fp2=StaticModInt;type Fp3=StaticModInt;pub fn convolution_arbitrary_mod(a:&[T],b:&[T])->Vec{if a.len().min(b.len())<60{return convolution_naive(a,b);}let a1=a.iter().map(|&x|Fp1::new(x.val())).collect::>();let a2=a.iter().map(|&x|Fp2::new(x.val())).collect::>();let a3=a.iter().map(|&x|Fp3::new(x.val())).collect::>();let b1=b.iter().map(|&x|Fp1::new(x.val())).collect::>();let b2=b.iter().map(|&x|Fp2::new(x.val())).collect::>();let b3=b.iter().map(|&x|Fp3::new(x.val())).collect::>();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_0_1_0 {use crate::__cargo_equip::preludes::__convolution_naive_0_1_0::*;use modint::ModInt;pub fn convolution_naive(a:&[T],b:&[T])->Vec{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(a:&mut[StaticModInt

]){assert!(StaticModInt::

::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::RATE2[(!s).trailing_zeros()as usize]);}}len+=1;}else{let p=1<::raw(1);let imag=StaticModInt::

::raw(StaticModInt::

::ROOT[2]);for s in 0..1<::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::

::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<::RATE3[(!s).trailing_zeros()as usize]);}}len+=2;}}}pub fn ntt_inv(a:&mut[StaticModInt

]){assert!(StaticModInt::

::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<::raw(1);for s in 0..1<::from((StaticModInt::

::modulus()+l.val()-r.val())as u64*irot.val()as u64,);}if s+1!=1<::raw(StaticModInt::

::IRATE2[(!s).trailing_zeros()as usize],);}}len-=1;}else{let p=1<::raw(1);let iimag=StaticModInt::

::raw(StaticModInt::

::IROOT[2]);for s in 0..1<::from((StaticModInt::

::modulus()as u64+a2-a3)*iimag.val()as u64,).val()as u64;a[i+offset]=StaticModInt::

::from(a0+a1+a2+a3);a[i+offset+p]=StaticModInt::

::from((a0+(StaticModInt::

::modulus()as u64-a1)+a2na3iimag)*irot.val()as u64,);a[i+offset+p*2]=StaticModInt::

::from((a0+a1+(StaticModInt::

::modulus()as u64-a2)+(StaticModInt::

::modulus()as u64-a3))*irot2.val()as u64,);a[i+offset+p*3]=StaticModInt::

::from((a0+(StaticModInt::

::modulus()as u64-a1)+(StaticModInt::

::modulus()as u64-a2na3iimag))*irot3.val()as u64,);}if s+1!=1<::raw(StaticModInt::

::IRATE3[(!s).trailing_zeros()as usize],);}}len-=2;}}let inv_n=StaticModInt::

::new(n).inv();for x in a.iter_mut(){*x*=inv_n;}}pub fn ntt_doubling(a:&mut Vec>){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::

::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(mut a:Vec>,mut b:Vec>,)->Vec>{let n=a.len();let m=b.len();if n==0||m==0{return vec![];}else 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 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,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};#[derive(Default,Clone,PartialEq,Eq)]#[repr(transparent)]pub struct FormalPowerSeries(pub Vec>);#[derive(Default,Clone,PartialEq,Eq)]#[repr(transparent)]pub struct SparseFormalPowerSeries(pub Vec<(usize,StaticModInt

)>);pub type FormalPowerSeries998244353=FormalPowerSeries<998_244_353>;pub type FormalPowerSeries1000000007=FormalPowerSeries<1_000_000_007>;pub type SparseFormalPowerSeries998244353=SparseFormalPowerSeries<998_244_353>;pub type SparseFormalPowerSeries1000000007=SparseFormalPowerSeries<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)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_formal_power_series_sfps{($(($d:expr,$x:expr)),*)=>($crate::__cargo_equip::crates::formal_power_series::SparseFormalPowerSeries(vec![$(($d,modint::StaticModInt::from($x))),*]));}macro_rules!sfps{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_formal_power_series_sfps!{$($tt)*})}implFormalPowerSeries

{pub fn shrink(&mut self){while self.last()==Some(&0.into()){self.pop();}}pub fn pre(mut self,d:usize)->Self{self.truncate(d);self}pub fn eval(&self,x:StaticModInt

)->StaticModInt

{let mut r=0.into();let mut w=StaticModInt::new(1);for&v in&self.0{r+=w*v;w*=x;}r}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::

::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 inv(&self,d:usize)->Self{assert_ne!(self[0].val(),0);if StaticModInt::

::IS_NTT_FRIENDLY{let mut res=fps![0;d];res[0]=self[0].inv();for k in 0..{let k=1<=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..{if k>=d{break;}let k=1<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::

::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<=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<=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

{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<=d/k{return fps![0;d];}}fps![0;d]}pub fn sqrt(&self,d:usize)->Option>{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{break;}res=(&res+self.clone().pre(i<<1)*res.inv(i<<1))*inv2;}Some(res.pre(d))}pub fn multipoint_evaluate(&self,xs:&[StaticModInt

])->Vec>{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%&g[1];for i in 2..m2+m{g[i]=&g[i>>1]%&g[i];}(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

)->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}}implSparseFormalPowerSeries

{pub fn normalize(&mut self){if self.len()==0{return;}self.0.sort_by_key(|&(i,_)|i);let mut res=Self(vec![(self[0].0,StaticModInt::new(0))]);for&(i,v)in&self.0{if res.len()==0||res.last().unwrap().0!=i{res.push((i,v));}else{res.last_mut().unwrap().1+=v;}}if res.len()!=0&&res.last().unwrap().1.val()==0{res.pop();}*self=res;}pub fn differential(&self)->Self{Self(self.iter().filter_map(|&(i,v)|(i>0).then(||(i-1,v*i))).collect(),)}pub fn integral(&self)->Self{Self(self.iter().map(|&(i,v)|(i+1,v/(i+1))).collect())}pub fn inv(self,d:usize)->FormalPowerSeries

{let mut f=fps![0;d];f[0]+=1;f/=self;f}pub fn log(self,d:usize)->FormalPowerSeries

{assert!(self[0].0==0&&self[0].1.val()==1);let f=self.differential();let mut res=(self.inv(d)*f).pre(d-1).integral();res.resize(d,0.into());res}pub fn exp(&self,d:usize)->FormalPowerSeries

{if self.len()==0{let mut res=fps![0;d];if d>0{res[0]=1.into();}return res;}assert_ne!(self[0].0,0);let mut res=fps![0;d];if d==0{return res;}let mut a=self.differential();for(d,_)in a.iter_mut(){*d+=1;}res[0]=1.into();let mut inv=vec![StaticModInt::

::new(1);d];let m=StaticModInt::

::modulus()as usize;for i in 1..d{if i>1{inv[i]=-inv[m%i]*(m/i);}res[i]=a.iter().filter_map(|&(j,v)|(i>=j).then(||v*res[i-j])).sum::>()*inv[i];}res}pub fn pow(&self,k:usize,d:usize)->FormalPowerSeries

{let offset=self.iter().position(|&(_,v)|v.val()!=0);let mut res=fps![0;d];if offset.is_none(){if k==0{res[0]+=1;}return res;}let offset=offset.unwrap();if self[offset].0>0{let deg=self[offset].0;if k>(d-1)/deg{return res;}let g=Self(self.iter().filter_map(|&(i,v)|(i>=deg).then(||(i-deg,v))).collect(),);let t=g.pow(k,d-k*deg);for i in 0..d-k*deg{res[k*deg+i]=t[i];}return res;}let mut inv=vec![StaticModInt::

::new(1);d+1];let m=P as usize;for i in 2..=d{inv[i]=-inv[m%i]*(m/i);}res[0]=self[0].1.pow(k);let c=self[0].1.inv();for i in 1..d{for&(j,v)in self.iter().skip(1).filter(|&&(j,_)|i>=j){res[i]=res[i]+v*res[i-j]*(StaticModInt::

::new(k)*j-(i-j));}res[i]*=inv[i]*c;}res}pub fn sqrt(&self,d:usize)->Option>{if self.len()==0{return Some(fps![0;d]);}let p=self[0].0;if p&1!=0{return None;}else if p/2>=d{return Some(fps![0;d]);}let inv_f0=self[0].1.inv();let lz=p/2;let mut g=fps![0;d];g[lz]=self[0].1.sqrt()?;let k=StaticModInt::new(2).inv();let mut inv=vec![StaticModInt::new(1);d];let m=P as usize;for i in 2..d{inv[i]=-inv[m%i]*(m/i);}for i in 1..d-lz{g[lz+i]=self.iter().skip(1).filter_map(|&(j,v)|(j-p<=i).then(||(j-p,v))).map(|(j,v)|v*g[lz+i-j]*(k*j-(i-j))).sum::>()*inv[i]*inv_f0;}Some(g)}}implDebug for FormalPowerSeries

{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{:?}",&self.0))}}implDisplay for FormalPowerSeries

{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(())}}implDebug for SparseFormalPowerSeries

{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{:?}",&self.0))}}implDeref for FormalPowerSeries

{type Target=Vec>;fn deref(&self)->&Self::Target{&self.0}}implDeref for SparseFormalPowerSeries

{type Target=Vec<(usize,StaticModInt

)>;fn deref(&self)->&Self::Target{&self.0}}implDerefMut for FormalPowerSeries

{fn deref_mut(&mut self)->&mut Self::Target{&mut self.0}}implDerefMut for SparseFormalPowerSeries

{fn deref_mut(&mut self)->&mut Self::Target{&mut self.0}}implFrom>>for FormalPowerSeries

{fn from(v:Vec>)->Self{Self(v)}}implFrom)>>for SparseFormalPowerSeries

{fn from(v:Vec<(usize,StaticModInt

)>)->Self{Self(v)}}implFrom>for FormalPowerSeries

{fn from(f:SparseFormalPowerSeries

)->Self{if f.len()==0{return fps![];}let mut g=FormalPowerSeries(vec![0.into();f.last().unwrap().0+1]);for(i,v)in f.0{g[i]+=v;}g}}implFrom>for SparseFormalPowerSeries

{fn from(f:FormalPowerSeries

)->Self{Self(f.0.into_iter().enumerate().collect())}}implNeg for FormalPowerSeries

{type Output=Self;fn neg(mut self)->Self::Output{for v in self.iter_mut(){*v=-*v;}self}}implNeg for SparseFormalPowerSeries

{type Output=Self;fn neg(mut self)->Self::Output{for(_,v)in self.iter_mut(){*v=-*v;}self}}implNeg for&FormalPowerSeries

{type Output=FormalPowerSeries

;fn neg(self)->Self::Output{-self.clone()}}implNeg for&SparseFormalPowerSeries

{type Output=SparseFormalPowerSeries

;fn neg(self)->Self::Output{-self.clone()}}implMulAssign>for FormalPowerSeries

{fn mul_assign(&mut self,rhs:StaticModInt

){for v in self.iter_mut(){*v*=rhs;}}}implMulAssign>for SparseFormalPowerSeries

{fn mul_assign(&mut self,rhs:StaticModInt

){for(_,v)in self.iter_mut(){*v*=rhs;}}}implDivAssign>for FormalPowerSeries

{fn div_assign(&mut self,rhs:StaticModInt

){*self*=rhs.inv();}}implDivAssign>for SparseFormalPowerSeries

{fn div_assign(&mut self,rhs:StaticModInt

){*self*=rhs.inv();}}implAddAssignfor FormalPowerSeries

{fn add_assign(&mut self,rhs:Self){if self.len()AddAssignfor SparseFormalPowerSeries

{fn add_assign(&mut self,rhs:Self){let mut res=sfps![];let n=self.len();let m=rhs.len();let mut i=0;let mut j=0;while iAddAssign>for FormalPowerSeries

{fn add_assign(&mut self,rhs:SparseFormalPowerSeries

){if rhs.len()==0{return;}let m=rhs.last().unwrap().0+1;if self.len()SubAssignfor FormalPowerSeries

{fn sub_assign(&mut self,rhs:Self){if self.len()SubAssignfor SparseFormalPowerSeries

{fn sub_assign(&mut self,rhs:Self){*self+=-rhs;}}implSubAssign>for FormalPowerSeries

{fn sub_assign(&mut self,rhs:SparseFormalPowerSeries

){*self+=-rhs;}}implMulAssignfor FormalPowerSeries

{fn mul_assign(&mut self,rhs:Self){if StaticModInt::

::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);}}}implMulAssignfor SparseFormalPowerSeries

{fn mul_assign(&mut self,rhs:Self){self.0=self.0.drain(..).map(|(i,x)|rhs.iter().map(move|(j,y)|(i+j,x*y))).flatten().collect::>();self.normalize();}}implMulAssign>for FormalPowerSeries

{fn mul_assign(&mut self,rhs:SparseFormalPowerSeries

){if self.len()==0||rhs.len()==0{self.clear();return;}let n=self.len();self.resize(n+rhs.last().unwrap().0,0.into());let c=if rhs[0].0==0{rhs[0].1}else{0.into()};for i in(0..n).rev(){for&(j,v)in rhs.iter().rev(){if j==0{continue;}self[i+j]=self[i+j]+self[i]*v;}self[i]*=c;}}}implDivAssignfor FormalPowerSeries

{fn div_assign(&mut self,mut g:Self){if self.len()DivAssign>for FormalPowerSeries

{fn div_assign(&mut self,mut rhs:SparseFormalPowerSeries

){assert_eq!(rhs[0].0,0);let c=rhs[0].1.inv();self.iter_mut().for_each(|v|*v*=c);rhs.iter_mut().for_each(|(_,v)|*v*=c);for i in 0..self.len(){for&(j,v)in rhs.iter().filter(|&&(j,_)|j>0&&i>=j){self[i]=self[i]-self[i-j]*v;}}}}implRemAssignfor FormalPowerSeries

{fn rem_assign(&mut self,rhs:Self){*self-=self.clone()/&rhs*&rhs;self.shrink();}}implShlAssignfor FormalPowerSeries

{fn shl_assign(&mut self,rhs:usize){self.0=repeat(0.into()).take(rhs).chain(self.0.drain(..)).collect();}}implShlAssignfor SparseFormalPowerSeries

{fn shl_assign(&mut self,rhs:usize){self.iter_mut().for_each(|(i,_)|*i+=rhs);}}implShrAssignfor FormalPowerSeries

{fn shr_assign(&mut self,rhs:usize){self.0=self.0.drain(rhs..).collect();}}implShrAssignfor SparseFormalPowerSeries

{fn shr_assign(&mut self,rhs:usize){self.0=self.0.drain(..).filter_map(|(i,v)|(i>=rhs).then(||(i-rhs,v))).collect();}}macro_rules!impl_ops{($($ty_l:ty,$ty_r:ty,$trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl$trait_assign<&$ty_r>for$ty_l{fn$fn_assign(&mut self,rhs:&$ty_r){self.$fn_assign(rhs.clone());}}impl$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$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$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$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

,StaticModInt

,Mul,MulAssign,mul,mul_assign,FormalPowerSeries

,StaticModInt

,Div,DivAssign,div,div_assign,FormalPowerSeries

,FormalPowerSeries

,Add,AddAssign,add,add_assign,FormalPowerSeries

,FormalPowerSeries

,Sub,SubAssign,sub,sub_assign,FormalPowerSeries

,FormalPowerSeries

,Mul,MulAssign,mul,mul_assign,FormalPowerSeries

,FormalPowerSeries

,Div,DivAssign,div,div_assign,FormalPowerSeries

,FormalPowerSeries

,Rem,RemAssign,rem,rem_assign,FormalPowerSeries

,usize,Shl,ShlAssign,shl,shl_assign,FormalPowerSeries

,usize,Shr,ShrAssign,shr,shr_assign,SparseFormalPowerSeries

,StaticModInt

,Mul,MulAssign,mul,mul_assign,SparseFormalPowerSeries

,StaticModInt

,Div,DivAssign,div,div_assign,SparseFormalPowerSeries

,SparseFormalPowerSeries

,Add,AddAssign,add,add_assign,SparseFormalPowerSeries

,SparseFormalPowerSeries

,Sub,SubAssign,sub,sub_assign,SparseFormalPowerSeries

,SparseFormalPowerSeries

,Mul,MulAssign,mul,mul_assign,SparseFormalPowerSeries

,usize,Shl,ShlAssign,shl,shl_assign,SparseFormalPowerSeries

,usize,Shr,ShrAssign,shr,shr_assign,FormalPowerSeries

,SparseFormalPowerSeries

,Add,AddAssign,add,add_assign,FormalPowerSeries

,SparseFormalPowerSeries

,Sub,SubAssign,sub,sub_assign,FormalPowerSeries

,SparseFormalPowerSeries

,Mul,MulAssign,mul,mul_assign,FormalPowerSeries

,SparseFormalPowerSeries

,Div,DivAssign,div,div_assign,}} pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy(Cell>,Once);implLazy{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe implSync for Lazy{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize(lazy:&T){LazyStatic::initialize(lazy);}} pub mod mo {pub trait Mo{type Output:Default+Clone;#[allow(unused_variables)]fn add(&mut self,i:usize){unimplemented!()}#[allow(unused_variables)]fn remove(&mut self,i:usize){unimplemented!()}fn add_left(&mut self,i:usize){self.add(i);}fn add_right(&mut self,i:usize){self.add(i);}fn remove_left(&mut self,i:usize){self.remove(i);}fn remove_right(&mut self,i:usize){self.remove(i);}fn query(&self)->Self::Output;fn solve(&mut self,qs:&[(usize,usize)])->Vec{let n=qs.iter().map(|&(_,r)|r).max().unwrap();let q=qs.len();let w=n/n.max(1).min((q.max(1)as f64).sqrt().round()as usize);let mut ord=(0..q).collect::>();ord.sort_by_key(|&i|{let(l,r)=qs[i];(l/w,if(l/w)&1==0{r}else{!r})});let mut l=0;let mut r=0;let mut res=vec![Default::default();q];for i in ord{let(ll,rr)=qs[i];while l>ll{l-=1;self.add_left(l);}while rrr{r-=1;self.remove_right(r);}res[i]=self.query();}res}}} pub mod 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},};#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct StaticModInt(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+FromStr+From+From+From+From+From+From+From+From+From+From+From+From+Copy+Eq+Hash+fmt::Display+fmt::Debug+Neg+Add+Sub+Mul+Div+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;}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 ix 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(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{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*xModInt for StaticModInt

{#[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.sqrt()}}implStaticModInt

{#[inline]pub fn new>>(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{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<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.sqrt()}}impl DynamicModInt{#[inline]pub fn new>(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{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<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);implFromStr for StaticModInt

{type Err=ParseIntError;fn from_str(s:&str)->Result{s.parse::().map(Self::from)}}impl FromStr for DynamicModInt{type Err=ParseIntError;fn from_str(s:&str)->Result{s.parse::().map(Self::from)}}implfmt::Display for StaticModInt

{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)}}implfmt::Debug for StaticModInt

{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)),*)=>{$(implFrom<$t1>for StaticModInt

{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>AddAssignfor StaticModInt

{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=P{self.0-=P;}}}impl>AddAssignfor DynamicModInt{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=Self::modulus(){self.0-=Self::modulus();}}}impl>SubAssignfor StaticModInt

{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0>SubAssignfor DynamicModInt{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0>MulAssignfor StaticModInt

{fn mul_assign(&mut self,rhs:T){*self=Self((self.0 as u64*rhs.into().0 as u64%P as u64)as u32);}}impl>MulAssignfor DynamicModInt{fn mul_assign(&mut self,rhs:T){*self=Self(BARRETT.mul(self.0,rhs.into().0));}}impl>DivAssignfor StaticModInt

{fn div_assign(&mut self,rhs:T){*self*=rhs.into().inv()}}impl>DivAssignfor DynamicModInt{fn div_assign(&mut self,rhs:T){*self=*self*rhs.into().inv()}}implNeg for StaticModInt

{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)}}}implNeg for&StaticModInt

{type Output=StaticModInt

;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$trait_assign<&StaticModInt

>for StaticModInt

{fn$fn_assign(&mut self,rhs:&StaticModInt

){self.$fn_assign(*rhs);}}impl>>$traitfor StaticModInt

{type Output=StaticModInt

;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl$trait<&StaticModInt

>for StaticModInt

{type Output=StaticModInt

;fn$fn(self,rhs:&StaticModInt

)->Self::Output{self.$fn(*rhs)}}impl>>$traitfor&StaticModInt

{type Output=StaticModInt

;fn$fn(self,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl$trait<&StaticModInt

>for&StaticModInt

{type Output=StaticModInt

;fn$fn(self,rhs:&StaticModInt

)->Self::Output{(*self).$fn(*rhs)}}impl$trait_assign<&DynamicModInt>for DynamicModInt{fn$fn_assign(&mut self,rhs:&DynamicModInt){self.$fn_assign(*rhs);}}impl>$traitfor 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>$traitfor&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,}implSum for StaticModInt

{fn sum>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}implProduct for StaticModInt

{fn product>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}impl<'a,const P:u32>Sum<&'a Self>for StaticModInt

{fn sum>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}impl<'a,const P:u32>Product<&'a Self>for StaticModInt

{fn product>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}implStaticModInt

{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;}} pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource{tokens:Peekable>,current_context:Box,reader:R,}implLineSource{pub fn new(reader:R)->LineSource{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}implSourcefor LineSource{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource>{fn from(s:&'a str)->LineSource>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource{tokens:Peekable>,context:Box,_read:PhantomData,}implOnceSource{pub fn new(mut source:R)->OnceSource{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}implSourcefor OnceSource{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource>{fn from(s:&'a str)->OnceSource>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl>Sourcefor&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read>(source:&mut S)->Self::Output;}implReadable for T where T::Err:Debug,{type Output=T;fn read>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input. ","This is a bug in `proconio`. ","Please report this issue from ","."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));lock.is_empty()}} } pub(crate) mod macros { pub mod __convolution_arbitrary_mod_0_1_0 {} pub mod __convolution_naive_0_1_0 {} pub mod convolution_ntt_friendly {} pub mod formal_power_series {pub use crate::{__cargo_equip_macro_def_formal_power_series_fps as fps,__cargo_equip_macro_def_formal_power_series_sfps as sfps};} pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};} pub mod mo {} pub mod modint {} pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};} } pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};} mod preludes { pub mod __convolution_arbitrary_mod_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__convolution_naive_0_1_0 as convolution_naive,convolution_ntt_friendly,modint};} pub mod __convolution_naive_0_1_0 {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_0_1_0 as convolution_naive,modint};} pub mod formal_power_series {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__convolution_arbitrary_mod_0_1_0 as convolution_arbitrary_mod,convolution_ntt_friendly,modint};} pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;} pub mod mo {} pub mod modint {} pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__lazy_static_1_4_0 as lazy_static;} } }