結果

問題 No.502 階乗を計算するだけ
ユーザー LenqthLenqth
提出日時 2023-10-23 02:48:18
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 988 ms / 1,000 ms
コード長 58,810 bytes
コンパイル時間 15,686 ms
コンパイル使用メモリ 389,740 KB
実行使用メモリ 29,432 KB
最終ジャッジ日時 2024-09-22 09:57:34
合計ジャッジ時間 27,974 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 85 ms
25,328 KB
testcase_05 AC 80 ms
25,304 KB
testcase_06 AC 82 ms
25,152 KB
testcase_07 AC 76 ms
25,272 KB
testcase_08 AC 75 ms
25,376 KB
testcase_09 AC 80 ms
25,336 KB
testcase_10 AC 76 ms
25,264 KB
testcase_11 AC 80 ms
25,260 KB
testcase_12 AC 81 ms
25,444 KB
testcase_13 AC 79 ms
25,348 KB
testcase_14 AC 78 ms
25,316 KB
testcase_15 AC 79 ms
25,272 KB
testcase_16 AC 85 ms
25,264 KB
testcase_17 AC 86 ms
25,368 KB
testcase_18 AC 84 ms
25,292 KB
testcase_19 AC 75 ms
25,380 KB
testcase_20 AC 78 ms
25,148 KB
testcase_21 AC 82 ms
25,344 KB
testcase_22 AC 101 ms
25,492 KB
testcase_23 AC 89 ms
25,400 KB
testcase_24 AC 93 ms
25,580 KB
testcase_25 AC 84 ms
25,364 KB
testcase_26 AC 95 ms
25,380 KB
testcase_27 AC 84 ms
25,452 KB
testcase_28 AC 95 ms
25,404 KB
testcase_29 AC 86 ms
25,364 KB
testcase_30 AC 97 ms
25,412 KB
testcase_31 AC 97 ms
25,400 KB
testcase_32 AC 967 ms
28,708 KB
testcase_33 AC 979 ms
29,228 KB
testcase_34 AC 951 ms
28,380 KB
testcase_35 AC 500 ms
27,276 KB
testcase_36 AC 977 ms
28,964 KB
testcase_37 AC 956 ms
28,636 KB
testcase_38 AC 983 ms
29,432 KB
testcase_39 AC 974 ms
29,120 KB
testcase_40 AC 478 ms
26,740 KB
testcase_41 AC 988 ms
29,336 KB
testcase_42 AC 1 ms
6,940 KB
testcase_43 AC 1 ms
6,940 KB
testcase_44 AC 1 ms
6,944 KB
testcase_45 AC 1 ms
6,944 KB
testcase_46 AC 1 ms
6,944 KB
testcase_47 AC 1 ms
6,940 KB
testcase_48 AC 1 ms
6,940 KB
testcase_49 AC 1 ms
6,944 KB
testcase_50 AC 1 ms
6,940 KB
testcase_51 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused `Result` that must be used
  --> src/main.rs:31:5
   |
31 |     stdout.write_fmt(format_args!("{}\n", factorial_large::<Mod1000000007>(n)));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: this `Result` may be an `Err` variant, which should be handled
   = note: `#[warn(unused_must_use)]` on by default
help: use `let _ = ...` to ignore the resulting value
   |
31 |     let _ = stdout.write_fmt(format_args!("{}\n", factorial_large::<Mod1000000007>(n)));
   |     +++++++

warning: unused `Result` that must be used
  --> src/main.rs:32:5
   |
32 |     stdout.flush();
   |     ^^^^^^^^^^^^^^
   |
   = note: this `Result` may be an `Err` variant, which should be handled
help: use `let _ = ...` to ignore the resulting value
   |
32 |     let _ = stdout.flush();
   |     +++++++

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use minimal_lib_int::modulo::Mod1000000007;
use minimal_lib_poly::poly::multipoint::factorial_large;

use std::{fmt::Debug, io::BufRead, str::FromStr};
fn read<T: FromStr>(r: &mut impl BufRead, buf: &mut Vec<u8>, d: u8) -> T
where
    <T as FromStr>::Err: Debug,
{
    buf.clear();
    let _b = r.read_until(d, buf);
    std::str::from_utf8(buf)
        .unwrap()
        .trim()
        .parse::<T>()
        .unwrap()
}

fn main() {
    use std::io::{stdin, stdout, BufReader, BufWriter, Write};
    let si = stdin();
    let mut sc = BufReader::new(si.lock());
    let mut buf = Vec::with_capacity(1024);

    let so = stdout();
    let mut stdout = BufWriter::new(so.lock());

    let n: usize = read(&mut sc, &mut buf, b'\n');

    stdout.write_fmt(format_args!("{}\n", factorial_large::<Mod1000000007>(n)));
    stdout.flush();
}

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

///  # Bundled libraries
/// 
///  - `minimal-lib-algo 0.1.0 (path+██████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_algo`
///  - `minimal-lib-int 0.2.0 (path+█████████████████████████████████)`   published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_int`
///  - `minimal-lib-poly 0.1.0 (path+██████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_poly`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod minimal_lib_algo {pub mod bisect{use std::ops::{Add,Shr};use std::cmp::PartialOrd;pub fn bisect_predicate_max<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r+one;while(l+one)<r{let h=(l+r)>>one;if f(h){unchanged=false;l=h;}else{r=h;}}if unchanged&&!f(l){return None;}Some(l)}pub fn bisect_predicate_min<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r;if!f(r){return None;}while(l+one)<r{let h=(l+r)>>one;if f(h){r=h;}else{unchanged=false;l=h;}}if unchanged&&f(l){return Some(l);}Some(r)}}pub mod compress{use std::{collections::{BTreeMap,HashMap},hash::Hash,};pub struct Compress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:HashMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>Compress<T>{pub fn new(it:&[T])->Compress<T>{let mut count=0;let mut last=None;let mut to_index=HashMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn is_empty(&self)->bool{self.count==0}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}#[derive(Debug)]pub struct SegmentCompress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:BTreeMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>SegmentCompress<T>{pub fn new<'a>(it:&[T])->Self{let mut count=0;let mut last=None;let mut to_index=BTreeMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{last=Some(y);continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn get_range(&self,left:T,right:T)->Option<(usize,usize)>{let mut rn=self.to_index.range(left.clone()..right.clone());let mut rn2=self.to_index.range(left..right);Some((*rn.next()?.1,*rn2.next_back()?.1))}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}}pub mod runlength{pub fn runlength<T>(xs:&[T])->Vec<(T,usize)>where T:Eq+Clone,{let mut result=vec![];let mut run=1;let mut prev_index=0;for(index,item)in xs.iter().enumerate().skip(1){if item==&xs[prev_index]{run+=1;}else{result.push((xs[prev_index].clone(),run));prev_index=index;run=1;}}result.push((xs[prev_index].clone(),run));result}}pub mod uf{pub struct UnionFind{vec:Vec<usize>,component_size:Vec<usize>,}impl UnionFind{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push(i);component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->usize{let mut a=a;let mut stack=Vec::new();loop{let parent=self.vec[a];if parent==a{for i in stack{self.vec[i]=a;}return a;}else{stack.push(a);a=parent;}}}pub fn union(&mut self,a:usize,b:usize){let a_root=self.find_root(a);let b_root=self.find_root(b);if a_root!=b_root{self.vec[a_root]=b_root;self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->bool{self.find_root(a)==self.find_root(b)}}pub trait Group:Default{fn mul(&self,rhs:&Self)->Self;fn inv(&self)->Self;}#[derive(Debug)]pub struct UnionFindWith<T:Group>{vec:Vec<(usize,T)>,component_size:Vec<usize>,}impl<T:Group+Copy+std::fmt::Debug>UnionFindWith<T>{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push((i,T::default()));component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->(usize,T){let mut a=a;let mut accum=T::default();let mut stack:Vec<(usize,T)> =Vec::new();loop{let(parent,g)=&self.vec[a];if*parent==a{stack.push((a,accum));let root_accum=accum;for(i,g)in stack.into_iter(){let nx=accum.mul(&g.inv());self.vec[i]=(a,nx);}return(a,root_accum);}else{stack.push((a,accum));accum=accum.mul(g);a=*parent;}}}pub fn union(&mut self,a:usize,b:usize,g:T){let(a_root,ga)=self.find_root(a);let(b_root,gb)=self.find_root(b);if a_root!=b_root{self.vec[a_root]=(b_root,g.mul(&gb.mul(&ga.inv())));self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->Option<T>{let(ra,ga)=self.find_root(a);let(rb,gb)=self.find_root(b);if ra==rb{Some(ga.mul(&gb.inv()))}else{None}}}}pub mod monotone_minima{pub struct MonotoneMinima<'a,T:Ord>{rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>}impl<'a,T:Ord>MonotoneMinima<'a,T>{pub fn new(rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>)->Self{Self{rows,columns,func}}fn minima_recur(&self,result:&mut[usize],yl:usize,yr:usize,xl:usize,xr:usize){if yl==yr{return;}let mid=(yl+yr)/2;let mut pos=xl;let mut minimum_value=(self.func)(mid,xl);for i in(xl+1)..xr{let v=(self.func)(mid,i);if v<minimum_value{minimum_value=v;pos=i;}}result[mid]=pos;self.minima_recur(result,yl,mid,xl,pos+1,);self.minima_recur(result,mid+1,yr,pos,xr,);}pub fn minimas(&self)->Vec<usize>{let mut result=vec![0;self.rows];self.minima_recur(&mut result,0,self.rows,0,self.columns);result}}}pub mod interval_set{use std::collections::BTreeMap;#[derive(Debug,Clone,Default)]pub struct IntervalSet<T>where T:Ord+Copy{s:BTreeMap<T,T>,}impl<T>IntervalSet<T>where T:Ord+Copy{pub fn new()->Self{Self{s:BTreeMap::new()}}pub fn get(&self,x:T)->Option<(T,T)>{use std::ops::Bound::*;self.s.range((Unbounded,Included(x))).next_back().filter(|&(_l,r)|x<*r).map(|(x,y)|(*x,*y))}pub fn insert(&mut self,l:T,r:T){use std::ops::Bound::*;let(l,r)=if let Some((il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<=*ir{if*ir<r{*ir=r;}(*il,*ir)}else{self.s.insert(l,r);(l,r)}}else{self.s.insert(l,r);(l,r)};while let Some((il,ir))=self.s.range((Unbounded,Included(r))).next_back(){let il=*il;let ir=*ir;if l==il{break;}let cur_seg_r=self.s.get_mut(&l).unwrap();if r<ir{*cur_seg_r=ir;}self.s.remove(&il);}}pub fn remove(&mut self,l:T,r:T){use std::ops::Bound::*;if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let t=*ir;*ir=l;self.s.insert(r,t);}else if l<*ir{*ir=l;}};while let Some((il,ir))=self.s.range((Included(l),Excluded(r))).next(){let il=*il;let ir=*ir;let cur_seg_r=self.s.get_mut(&il).unwrap();if l<ir{*cur_seg_r=r;}self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<*ir{*ir=l;}};}pub fn intervals(&self)->Vec<(T,T)>{self.s.iter().map(|(x,y)|(*x,*y)).collect()}pub fn intersect(&mut self,l:T,r:T){use std::ops::Bound::*;while let Some((il,ir))=self.s.range((Unbounded,Excluded(l))).next(){let il=*il;let ir=*ir;self.s.remove(&il);if l<ir{self.s.insert(l,ir);}}while let Some((il,_ir))=self.s.range((Included(r),Unbounded)).next(){let il=*il;self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let _t=*ir;*ir=r;}};}pub fn append(&mut self,new:&Self){for(l,r)in new.intervals().into_iter(){self.insert(l,r);}}}}pub mod permutation{pub fn inverse_permutation(perm:&[usize])->Vec<usize>{let n=perm.len();let mut res=vec![0;n];for i in 0..n{res[perm[i]]=i;}res}pub fn composite_permutation(first:&[usize],second:&[usize])->Vec<usize>{debug_assert_eq!(first.len(),second.len());let n=first.len();let mut res=vec![0;n];for i in 0..n{res[i]=second[first[i]];}res}}pub mod trisect{use std::cmp::PartialOrd;use std::ops::{Add,Div,Sub};pub fn trisect_predicate_min<T,S>(mut f:impl FnMut(T)->S,l:T,r:T)->(T,S)where T:Add<T,Output=T>+Sub<T,Output=T>+Div<T,Output=T>+PartialOrd+From<i64>+Copy+From<i64>+std::fmt::Debug,S:Ord+Clone,{let one=1.into();let two=2.into();let three:T=3.into();let mut l=l;let mut r=r+one;while(l+two)<r{let h1=(l+l+r+one)/three;let h2=(l+r+r)/three;eprintln!("{:?} {:?} {:?} {:?}",l,h1,h2,r);assert!(l<h1);assert!(h1<h2);assert!(h2<r);let cmp=Ord::cmp(&f(h1),&f(h2));match cmp{std::cmp::Ordering::Less=>{r=h2;}std::cmp::Ordering::Equal=>{l=h1;r=h2;}std::cmp::Ordering::Greater=>{l=h1;}}}let mut c=vec![];while l<r{c.push((l,f(l)));l=l+one;}c.into_iter().min_by_key(|x|x.1.clone()).unwrap()}}}
        pub mod minimal_lib_int {use crate::__cargo_equip::preludes::minimal_lib_int::*;pub mod cache{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod mul{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub struct MulCache{pub accum:Vec<i64>,pub inv:Vec<i64>,pub accum_inv:Vec<i64>,pub n:usize,pub p:i64,}impl MulCache{pub fn new(p:i64,n:usize)->Self{let mut accum=vec![0;n];let mut inv=vec![0;n];let mut accum_inv=vec![0;n];accum[0]=1;accum[1]=1;inv[0]=0;inv[1]=1;accum_inv[0]=1;accum_inv[1]=1;for i in 2..n{let i=i as i64;accum[i as usize]=(accum[(i-1)as usize]*i)%p;inv[i as usize]=p-inv[(p%i)as usize]*(p/i)%p;accum_inv[i as usize]=(accum_inv[(i-1)as usize]*inv[i as usize])%p;}Self{accum,inv,accum_inv,n,p,}}pub fn extend(&mut self,n:usize){if self.n<n{let p=self.p;for i in self.n..n{let i=i as i64;self.accum.push((self.accum[(i-1)as usize]*i)%p);self.inv.push(p-self.inv[(p%i)as usize]*(p/i)%p);self.accum_inv.push((self.accum_inv[(i-1)as usize]*self.inv[i as usize])%p);}self.n=n;}}pub fn inv_fact(&self,n:i64)->i64{self.accum_inv[n as usize]}pub fn combin(&self,n:i64,k:i64)->i64{debug_assert!(n<self.n as i64);if n<0||k<0||n<k{return 0;}self.accum[n as usize]*(self.accum_inv[k as usize]*self.accum_inv[(n-k)as usize]%self.p)%self.p}}}mod fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::utils::{powmod,modinv,minimum_exponent};pub struct FFTCache{pub modulo:i64,pub g:i64,pub sum_e:Vec<i64>,pub sum_ie:Vec<i64>,pub montg_r:i64,pub montg_r1:i64,pub montg_r2:i64,pub montg_r3:i64,pub montg_rinv:i64,pub montg_ndash:i64,}impl FFTCache{fn primitive_root(m:i64)->i64{match m{2=>1,167772161=>3,469762049=>3,595591169=>3,645922817=>3,897581057=>3,998244353=>3,754974721=>11,_=>todo!(),}}pub fn new(m:i64)->Self{let primroot=Self::primitive_root(m);let mut es=vec![0;30];let mut ies=vec![0;30];let cnt2=(m-1).trailing_zeros()as usize;let mut e=powmod(primroot,(m-1)>>cnt2,m);let mut ie=modinv(e,m);for i in(2..=cnt2).rev(){es[i-2]=e;ies[i-2]=ie;e*=e;e%=m;ie*=ie;ie%=m;}let sum_e:Vec<i64> =es.iter().scan(1,|acc,e|{*acc*=e;*acc%=m;Some(*acc)}).collect();let sum_ie:Vec<i64> =ies.iter().scan(1,|acc,ie|{*acc*=ie;*acc%=m;Some(*acc)}).collect();let rex=minimum_exponent(m);let montg_r=1<<rex;let montg_r1=montg_r%m;let montg_r2=(montg_r1*montg_r1)%m;let montg_r3=(montg_r2*montg_r1)%m;let montg_rinv=modinv(montg_r1%m,m);let mut montg_ndash=0;{let mut temp=0;for i in 0..rex{if(temp&1)==0{temp+=m;montg_ndash+=1<<i;}temp>>=1;}}debug_assert_eq!((m*montg_ndash)%montg_r,montg_r-1);Self{modulo:m,g:primroot,sum_e,sum_ie,montg_r,montg_r1,montg_r2,montg_r3,montg_rinv,montg_ndash,}}}}pub use mul::MulCache;pub use fft::FFTCache;}pub mod utils{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod gcd{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub fn gcd(a:i64,b:i64)->i64{let t=(a|b).trailing_zeros();let mut a=a;let mut b=b;a>>=t;b>>=t;if a&1==1{std::mem::swap(&mut a,&mut b);}a>>=a.trailing_zeros();while a!=b{if a>b{a-=b;a>>=a.trailing_zeros();}else{b-=a;b>>=b.trailing_zeros();}}a<<t}pub fn modinv(a:i64,b:i64)->i64{if b==2{return a;}let m=b;let mut a=a;let mut b=b;let mut u=1;let mut v=0;while a>0{if a&1==0{a>>=1;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}else{if a<b{std::mem::swap(&mut a,&mut b);std::mem::swap(&mut u,&mut v);}a=(a-b)>>1;u-=v;if u<0{u+=m;}if u&1==0{u>>=1;}else{u+=m;u>>=1;}}}assert_eq!(b,1);v}pub fn modinv_u64(a:u64,b:u64)->u64{if b==2{return a;}let m=b;let mut a=a;let mut b=b;let mut u=1;let mut v=0;while a>0{if a&1==0{a>>=1;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}else{if a<b{std::mem::swap(&mut a,&mut b);std::mem::swap(&mut u,&mut v);}a=(a-b)>>1;if u<v{u+=m;}u-=v;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}}assert_eq!(b,1);v}}mod modulo{use crate::__cargo_equip::preludes::minimal_lib_int::*;use super::gcd::modinv;pub fn powmod_large(val:i64,rhs:i64,m:i64)->i64{if rhs<0{todo!()}let mut res=1_i128;let mut r=rhs as i128;let mut a=val as i128;let m=m as i128;while r>0{if r&1==1{res*=a;res%=m;}a*=a;a%=m;r>>=1;}res as i64}pub fn powmod(val:i64,rhs:i64,m:i64)->i64{if rhs<0{return modinv(powmod(val,-rhs,m),m);}let mut res=1;let mut r=rhs;let mut a=val;while r>0{if r&1==1{res*=a;res%=m;}a*=a;a%=m;r>>=1;}res}pub fn sqrt_mod(y:i64,p:i64)->Option<i64>{let y=y%p;if p==2{return Some(y);}if y==0{return Some(0);}let q=p-1;let m=q.trailing_zeros();let q=q>>m;if powmod(y,q<<(m-1),p)==p-1{return None;}let mut z=2;while powmod(z,q<<(m-1),p)!=p-1{z+=1;}let mut t=powmod(y,q,p);let mut x=powmod(y,(q+1)>>1,p);let mut u=powmod(z,q,p);if m>=2{for i in(0..=(m-2)).rev(){if powmod(t,1<<i,p)==p-1{t*=(u*u)%p;t%=p;x*=u;x%=p;}u*=u;u%=p;}}if x>p-x{x=p-x;}Some(x)}}mod util{use crate::__cargo_equip::preludes::minimal_lib_int::*;use minimal_lib_algo::bisect::bisect_predicate_max;pub fn isqrt(x:i64)->i64{bisect_predicate_max(|y|y*y<=x,0,x.min(1<<31)).unwrap()}pub fn i_kth_root(x:i64,k:i64)->i64{if x<=1{return x;}if k==1{return x;}let bs=63-x.leading_zeros();bisect_predicate_max(|y|{y.checked_pow(k as u32).map(|yk|yk<=x).unwrap_or_default()},1,x>>(bs-bs/k as u32-1),).unwrap()as _}pub fn digits(x:i64,base:i64)->Vec<i64>{if x==0{return vec![0];}let mut res=vec![];let mut t=x;while t>0{res.push(t%base);t/=base;}res.reverse();res}pub fn minimum_exponent(n:i64)->usize{(64-n.saturating_sub(1).leading_zeros())as _}}mod prelude{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub use super::gcd::{modinv,modinv_u64,gcd};pub use super::modulo::{powmod,powmod_large,sqrt_mod};pub use super::util::{digits,i_kth_root,isqrt,minimum_exponent};pub use super::gerner::{gerner,gerner_u64,gerner_batch};}mod gerner{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::utils::modinv;fn ex_euclid(a:i64,b:i64)->(i64,i64,i64){let mut a=a;let mut b=b;let mut c=1;let mut d=0;let mut e=0;let mut f=1;while a!=0{let q=b/a;let res=(b%a,a,d,c-d*q,f,e-f*q);a=res.0;b=res.1;c=res.2;d=res.3;e=res.4;f=res.5;}if b<0{e=-e;c=-c;b=-b;}(e,c,b)}fn modular_div(n:i64,m:i64,p:i64)->Option<i64>{let(e,_c,b)=ex_euclid(m,p);if n%b!=0{None}else{let q=(n/b)*e;let mut q=q%p;if q<0{q+=p;}Some(q)}}pub fn gerner(r:&[i64],m:&[i64],mm:i64)->Option<i64>{debug_assert_eq!(r.len(),m.len());let l=m.len();let mut cons=vec![0;l];let mut coeff=vec![1;l];let mut res=0;let mut r_coeff=1;for i in 0..l{let mut v=modular_div(r[i]-cons[i],coeff[i],m[i])?;if v<0{v+=m[i];}for j in i+1..l{cons[j]+=v*coeff[j];cons[j]%=m[j];coeff[j]*=m[i];coeff[j]%=m[j];}res=(res+v*r_coeff)%mm;r_coeff=(r_coeff*m[i])%mm;}Some(res)}pub fn gerner_batch(r:&[Vec<i64>],m:&[i64],mm:i64)->Vec<i64>{debug_assert_eq!(r.len(),m.len());let rl=r[0].len();let l=m.len();let mut cons=vec![vec![0i64;rl];l];let mut coeff=vec![1;l];let mut res=vec![0i64;rl];let mut r_coeff=1;for i in 0..l{let d=modinv(coeff[i],m[i]);let v:Vec<i64> =r[i].iter().zip(cons[i].iter()).map(|(&x,&c)|{let mut v=(x-c)*d;v%=m[i];if v<0{v+=m[i];}v}).collect();for j in i+1..l{cons[j].iter_mut().zip(v.iter()).for_each(|(c,&v)|{*c+=v*coeff[j];*c%=m[j];});coeff[j]*=m[i];coeff[j]%=m[j];}res.iter_mut().zip(v.iter()).for_each(|(r,&v)|{*r+=v*r_coeff;*r%=mm;});r_coeff=(r_coeff*m[i])%mm;}res}pub fn gerner_u64(r:&[u64])->u64{debug_assert!(r.len()<=5);let mut cons=[0;5];let m=[469762049,595591169,645922817,897581057,998244353];let coeff=[[1,1,1,1,1],[1,469762049,469762049,469762049,469762049],[1,469762049,44993443,300657119,491473740],[1,469762049,44993443,528892613,173461320],[1,469762049,44993443,528892613,202041274],];let coeff_inv=[1,436766862,35884648,19245542,390741676];let mut res:u64=0;let mut r_coeff:u64=1;for i in 0..r.len(){let mut v=if r[i]<cons[i]{(r[i]+m[i]-cons[i])%m[i]}else{r[i]-cons[i]};v=(v*coeff_inv[i])%m[i];for j in(i+1)..r.len(){cons[j]=cons[j].wrapping_add(v*coeff[i][j]);cons[j]%=m[j];}res=res.wrapping_add(v.wrapping_mul(r_coeff));r_coeff=r_coeff.wrapping_mul(m[i]);}res}}pub use prelude::*;}pub mod modulo{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod modulo_v2{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::{ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},marker::PhantomData,thread::LocalKey,usize,cell::RefCell};use crate::__cargo_equip::crates::minimal_lib_int::{utils::{powmod,modinv},cache::{MulCache,FFTCache}};use super::{Mod998244353,Mod1000000007};pub trait Field:Sized+Clone+Add<Self,Output=Self>+Sub<Self,Output=Self>+Neg<Output=Self>+Mul<Self,Output=Self>+Div<Self,Output=Self>{fn pow(self,rhs:i64)->Self;fn inv(self)->Self;fn zero()->Self;fn one()->Self;}pub trait Modulus:'static+Copy+Eq+Ord{const IS_PRIME:bool=false;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>;fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>;fn get_modulo()->i64;fn extend(n:usize){Self::mul_cache().with(|cache|cache.borrow_mut().extend(n));}}pub trait FFTModulus:Modulus{const EXP:usize;fn fft_cache()->&'static LocalKey<RefCell<FFTCache>>;}pub type ModInt998244353=ModInt<Mod998244353>;pub type ModInt1000000007=ModInt<Mod1000000007>;#[derive(Copy,Clone,Eq,PartialEq,PartialOrd,Ord)]#[repr(transparent)]pub struct ModInt<T:Modulus>{pub v:i64,ph:PhantomData<fn()->T>}impl<T:Modulus>std::fmt::Debug for ModInt<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{}",self.v))}}impl<T:Modulus>std::fmt::Display for ModInt<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{}",self.v))}}impl<T:Modulus>ModInt<T>{pub fn pow(self,rhs:i64)->Self{Self::new(powmod(self.v,rhs,T::get_modulo()))}pub fn inv(self)->Self{Self::new(modinv(self.v,T::get_modulo()))}pub fn zero()->Self{Self::new(0)}pub fn one()->Self{Self::new(1)}pub fn fact(n:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum=&cache.accum;Self::from(accum[n])})}pub fn combin(n:usize,k:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();Self::from(cache.combin(n as i64,k as i64))})}pub fn factinv(n:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum_inv=&cache.accum_inv;Self::from(accum_inv[n])})}}impl<T:Modulus>Field for ModInt<T>{fn pow(self,rhs:i64)->Self{Self::new(powmod(self.v,rhs,T::get_modulo()))}fn inv(self)->Self{Self::new(modinv(self.v,T::get_modulo()))}fn zero()->Self{Self::new(0)}fn one()->Self{Self::new(1)}}impl<T:Modulus>AsRef<ModInt<T>>for ModInt<T>{fn as_ref(&self)->&ModInt<T>{self}}impl<T:Modulus>Default for ModInt<T>{fn default()->Self{Self{v:0,ph:Default::default()}}}impl<T:Modulus>Add<Self>for ModInt<T>{type Output=Self;fn add(self,rhs:Self)->Self::Output{let r=self.v+rhs.v;if r>=T::get_modulo(){Self::new(r-T::get_modulo())}else{Self::new(r)}}}impl<T:Modulus>Sub<Self>for ModInt<T>{type Output=Self;fn sub(self,rhs:Self)->Self::Output{let r=self.v-rhs.v;if r<0{Self::new(r+T::get_modulo())}else{Self::new(r)}}}impl<T:Modulus>Mul<Self>for ModInt<T>{type Output=Self;fn mul(self,rhs:Self)->Self::Output{Self::new(self.v*rhs.v%T::get_modulo())}}impl<T:Modulus>Div<Self>for ModInt<T>{type Output=Self;fn div(self,rhs:Self)->Self::Output{self*rhs.inv()}}impl<T:Modulus>Neg for ModInt<T>{type Output=Self;fn neg(self)->Self{Self::new(if self.v!=0{T::get_modulo()-self.v}else{0})}}impl<T:Modulus>std::iter::Sum for ModInt<T>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{let mut acc=0;for x in iter.into_iter(){acc+=x.v;}acc%=T::get_modulo();Self::new(acc)}}impl<T:Modulus>AddAssign for ModInt<T>{fn add_assign(&mut self,rhs:Self){self.v+=rhs.v;if self.v>=T::get_modulo(){self.v-=T::get_modulo();}}}impl<T:Modulus>SubAssign for ModInt<T>{fn sub_assign(&mut self,rhs:Self){self.v-=rhs.v;if self.v<0{self.v+=T::get_modulo();}}}impl<T:Modulus>MulAssign for ModInt<T>{fn mul_assign(&mut self,rhs:Self){self.v*=rhs.v;self.v%=T::get_modulo();}}impl<T:Modulus>DivAssign for ModInt<T>{fn div_assign(&mut self,rhs:Self){self.v*=rhs.inv().v;self.v%=T::get_modulo();}}impl<T:Modulus>ModInt<T>{pub fn new(v:i64)->Self{debug_assert!(0<=v&&v<T::get_modulo());Self{v,ph:PhantomData}}}impl<T:Modulus>From<i32>for ModInt<T>{fn from(x:i32)->Self{let x=x as _;if x<0{ModInt::new(x%T::get_modulo()+T::get_modulo())}else if x<T::get_modulo(){ModInt::new(x)}else{ModInt::new(x%T::get_modulo())}}}impl<T:Modulus>From<i64>for ModInt<T>{fn from(x:i64)->Self{if x<0{ModInt::new(x%T::get_modulo()+T::get_modulo())}else if x<T::get_modulo(){ModInt::new(x)}else{ModInt::new(x%T::get_modulo())}}}impl<T:Modulus>From<usize>for ModInt<T>{fn from(x:usize)->Self{if(x as i64)<T::get_modulo(){ModInt::new(x as i64)}else{ModInt::new(x as i64%T::get_modulo())}}}impl<T:Modulus>From<ModInt<T>>for i64{fn from(x:ModInt<T>)->Self{x.v}}impl<T:Modulus>From<ModInt<T>>for usize{fn from(x:ModInt<T>)->Self{x.v as _}}impl<T:Modulus>From<ModInt<T>>for i32{fn from(x:ModInt<T>)->Self{x.v as _}}}mod modulos{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::{thread::LocalKey,cell::RefCell};use crate::__cargo_equip::crates::minimal_lib_int::{cache::{FFTCache,MulCache},fft::{modint_fft::convol,convol_u64::convol_modint}};use super::{FFTModulus,ModInt,Modulus};macro_rules!gen_static_modulo{($x:ident,$modulo:literal,$fft_exp:literal)=>{#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum$x{}impl$x{thread_local!{static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new($modulo,1000005));static FFT_CACHE:RefCell<FFTCache> =RefCell::new(FFTCache::new($modulo));}}impl FFTModulus for$x{const EXP:usize=$fft_exp;fn fft_cache()->&'static LocalKey<RefCell<FFTCache>>{&Self::FFT_CACHE}}impl Modulus for$x{fn get_modulo()->i64{$modulo}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol(x,y)}}};($x:ident,$modulo:literal)=>{#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum$x{}impl$x{thread_local!{static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new($modulo,1000005));}}impl Modulus for$x{fn get_modulo()->i64{$modulo}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol_modint(&x,&y)}}};}gen_static_modulo!{Mod469762049,469762049_i64,26}gen_static_modulo!{Mod595591169,595591169_i64,23}gen_static_modulo!{Mod645922817,645922817_i64,23}gen_static_modulo!{Mod998244353,998244353_i64,23}gen_static_modulo!{Mod1000000007,1000000007_i64}#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum ModDynamic{}impl ModDynamic{thread_local!{static DYNAMIC_MODULO:RefCell<i64> =RefCell::new(1000000007);static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new(1000000007_i64,5));}pub fn set_modulo(new_modulo:i64){Self::DYNAMIC_MODULO.with(|x|{*x.borrow_mut()=new_modulo;});Self::MUL_CACHE.with(|x|{*x.borrow_mut()=MulCache::new(new_modulo,5);});}}impl Modulus for ModDynamic{fn get_modulo()->i64{Self::DYNAMIC_MODULO.with(|x|{let x=*x.borrow();x})}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol_modint(x,y)}}}pub use modulo_v2::{FFTModulus,Field,ModInt,Modulus};pub use modulos::{Mod1000000007,Mod998244353,Mod469762049,Mod595591169,Mod645922817,ModDynamic};}pub mod fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub mod modint_fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::{modulo::{ModInt,FFTModulus},utils::minimum_exponent,};pub fn fft<T:FFTModulus>(v:&mut[ModInt<T>]){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();T::fft_cache().with(|cache|{let cache=cache.borrow();let sum_e=&cache.sum_e;for ph in 1..=h{let w=1<<(ph-1);let p=1<<(h-ph);let mut now=ModInt::one();for s in 0..w{let offset=s<<(h-ph+1);for i in offset..(p+offset){let l=v[i];let r=v[i+p]*now;v[i]=l+r;v[i+p]=l-r;}now*=ModInt::new(sum_e[(!s).trailing_zeros()as usize]);}}});}pub fn ifft<T:FFTModulus>(v:&mut[ModInt<T>]){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();T::fft_cache().with(|cache|{let cache=cache.borrow();let sum_ie=&cache.sum_ie;for ph in(1..=h).rev(){let w=1<<(ph-1);let p=1<<(h-ph);let mut inow=ModInt::one();for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=v[i+offset];let r=v[i+offset+p];v[i+offset]=l+r;v[i+offset+p]=(l-r)*inow;}inow*=ModInt::new(sum_ie[(!s).trailing_zeros()as usize]);}}});}pub fn convol<T:FFTModulus>(x:&[ModInt<T>],y:&[ModInt<T>])->Vec<ModInt<T>>{if x.is_empty()||y.is_empty(){return vec![];}let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans=vec![ModInt::zero();xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]+=a[i]*b[j];}}return ans;}let zl=xl+yl-1;let(mut x,mut y)=(x.to_owned(),y.to_owned());let z=1<<minimum_exponent(zl as _);x.resize(z,ModInt::zero());fft(&mut x);y.resize(z,ModInt::zero());fft(&mut y);for i in 0..z{x[i]*=y[i];}ifft(&mut x);x.resize(zl,ModInt::zero());let iz=ModInt::from(z as i64).inv();for i in 0..zl{x[i]*=iz;}x}pub fn convol_in<T:FFTModulus>(x:&mut[ModInt<T>],y:&[ModInt<T>]){if x.is_empty()||y.is_empty(){return;}let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let mut ans=vec![ModInt::zero();xl];for i in 0..xl{for j in 0..yl{if i+j>=xl{break;}ans[i+j]+=x[i]*y[j];}}x.clone_from_slice(&ans[0..xl]);return;}let mut y=y.to_owned();fft(x);fft(&mut y);for i in 0..xl{x[i]*=y[i];}ifft(x);let iz=ModInt::from(xl as i64).inv();for i in 0..xl{x[i]*=iz;}}}pub mod relax_mult{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};use std::collections::VecDeque;const BITS:usize=64;pub struct RelaxedMul<T:Modulus>{index:usize,left:Vec<ModInt<T>>,right:Vec<ModInt<T>>,convolved:Vec<VecDeque<Vec<ModInt<T>>>>,}impl<T:Modulus>RelaxedMul<T>{pub fn new()->Self{RelaxedMul{index:0,left:Vec::new(),right:Vec::new(),convolved:vec![VecDeque::new();32],}}fn block_conv(&self,left:usize,right:usize,block_size:usize)->Vec<ModInt<T>>{let l=&self.left[left..left+block_size];let r=&self.right[right..right+block_size];T::convolution(l,r)}pub fn push(&mut self,left:ModInt<T>,right:ModInt<T>)->ModInt<T>{let mut block_type=(self.index+2)&(self.index+2).wrapping_neg();let index=self.index;self.left.push(left);self.right.push(right);if block_type>self.index{block_type>>=1;if block_type>1{for i in 1..BITS{let block_size=(1<<i)as usize;if block_size>=block_type{let block_min=block_size-1;let b=self.block_conv(block_min,block_min,block_size);self.convolved[i].push_back(b);break;}let block_min1=self.index+1-block_size;let block_min2=block_size-1;let b1=self.block_conv(block_min1,block_min2,block_size);let b2=self.block_conv(block_min2,block_min1,block_size);self.convolved[i].push_back(b1);self.convolved[i].push_back(b2);}}}else if block_type>1{for i in 1..BITS{let block_size=(1<<i)as usize;if block_size>block_type{break;}let block_min1=self.index+1-block_size;let block_min2=block_size-1;let b1=self.block_conv(block_min1,block_min2,block_size);let b2=self.block_conv(block_min2,block_min1,block_size);self.convolved[i].push_back(b1);self.convolved[i].push_back(b2);}}let mut sum=if index>0{left*self.right[0]+right*self.left[0]}else{left*right};for i in 1..BITS{while self.convolved[i].len()>4{self.convolved[i].pop_front();}let q=(index+2)%(1<<i);match self.convolved[i].len(){0=>{break;}1=>{sum+=self.convolved[i][0][q];}3=>{if q<(1<<i)-1{sum+=self.convolved[i][0][q+(1<<i)];}sum+=self.convolved[i][1][q];sum+=self.convolved[i][2][q];}4=>{if q<(1<<i)-1{sum+=self.convolved[i][0][q+(1<<i)];sum+=self.convolved[i][1][q+(1<<i)];}sum+=self.convolved[i][2][q];sum+=self.convolved[i][3][q];}_=>todo!(),}}self.index+=1;sum}}}pub mod convol_u64{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};use crate::__cargo_equip::crates::minimal_lib_int::{cache::FFTCache,utils::modinv_u64,utils::minimum_exponent,};use crate::__cargo_equip::crates::minimal_lib_int::utils::{gerner_u64,gerner,gerner_batch};pub fn fft_mod_u64(v:&mut[u64],cache:&FFTCache){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();let FFTCache{sum_e,modulo,..}=cache;let modulo=*modulo as u64;for ph in 1..=h{let w=1<<(ph-1);let p=1<<(h-ph);let mut now=1;for s in 0..w{let offset=s<<(h-ph+1);for i in offset..(p+offset){let l=v[i];let mut r=v[i+p]*now;r%=modulo;v[i]=(l+r)%modulo;if l>r{v[i+p]=l-r;}else{v[i+p]=(l+(modulo-r))%modulo;}}now*=sum_e[(!s).trailing_zeros()as usize]as u64;now%=modulo;}}}pub fn ifft_mod_u64(v:&mut[u64],cache:&FFTCache){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();let FFTCache{sum_ie,modulo,..}=cache;let modulo=*modulo as u64;for ph in(1..=h).rev(){let w=1<<(ph-1);let p=1<<(h-ph);let mut inow=1;for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=v[i+offset];let r=v[i+offset+p];v[i+offset]=(l+r)%modulo;let q=if l>r{l-r}else{(l+(modulo-r))%modulo};v[i+offset+p]=(q*inow)%modulo;}inow*=sum_ie[(!s).trailing_zeros()as usize]as u64;inow%=modulo;}}}pub fn convol_mod(x:&[u64],y:&[u64],cache:&FFTCache)->Vec<u64>{if x.is_empty()||y.is_empty(){return vec![];}let(xl,yl)=(x.len(),y.len());let zl:usize=xl+yl-1;let(mut x,mut y)=(x.to_owned(),y.to_owned());let z=1<<minimum_exponent(zl as _);let modulo=cache.modulo as u64;for i in 0..xl{x[i]%=modulo;}for i in 0..yl{y[i]%=modulo;}x.resize(z,0);fft_mod_u64(&mut x,cache);y.resize(z,0);fft_mod_u64(&mut y,cache);for i in 0..z{x[i]*=y[i];x[i]%=modulo;}ifft_mod_u64(&mut x,cache);x.resize(zl,0);let iz=modinv_u64(z as u64,modulo);for i in 0..zl{x[i]*=iz;x[i]%=modulo;}x}thread_local!{pub static MODULO_CACHES:Box<[FFTCache;5]> =Box::new([FFTCache::new(469762049),FFTCache::new(595591169),FFTCache::new(645922817),FFTCache::new(897581057),FFTCache::new(998244353)]);}pub fn convol_u64(x:&[u64],y:&[u64])->Vec<u64>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<u64> =vec![0;xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]=ans[i+j].wrapping_add(a[i].wrapping_mul(b[j]));}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,c4,c5]=cc.as_ref();let z1=convol_mod(x,y,c1);let z2=convol_mod(x,y,c2);let z3=convol_mod(x,y,c3);let z4=convol_mod(x,y,c4);let z5=convol_mod(x,y,c5);let mut result=vec![];for i in 0..z1.len(){result.push(gerner_u64(&[z1[i],z2[i],z3[i],z4[i],z5[i]]))}result})}pub fn convol_u32(x:&[u64],y:&[u64])->Vec<u64>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<u64> =vec![0;xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]=ans[i+j].wrapping_add(a[i].wrapping_mul(b[j]));}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,_c4,_c5]=cc.as_ref();let z1=convol_mod(x,y,c1);let z2=convol_mod(x,y,c2);let z3=convol_mod(x,y,c3);let mut result=vec![];let m=[c1.modulo,c2.modulo,c3.modulo];for i in 0..z1.len(){result.push(gerner(&[z1[i]as i64,z2[i]as i64,z3[i]as i64],&m,1000000007).unwrap()as u64)}result})}pub fn convol_modint<T:Modulus>(x:&[ModInt<T>],y:&[ModInt<T>])->Vec<ModInt<T>>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<_> =vec![ModInt::zero();xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]+=a[i]*b[j];}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,_c4,_c5]=cc.as_ref();let x:Vec<u64> =x.iter().map(|&i|i64::from(i)as u64).collect();let y:Vec<u64> =y.iter().map(|&i|i64::from(i)as u64).collect();let z1:Vec<i64> =convol_mod(&x,&y,c1).into_iter().map(|x|x as i64).collect();let z2:Vec<i64> =convol_mod(&x,&y,c2).into_iter().map(|x|x as i64).collect();let z3:Vec<i64> =convol_mod(&x,&y,c3).into_iter().map(|x|x as i64).collect();let m=[c1.modulo,c2.modulo,c3.modulo];gerner_batch(&[z1,z2,z3],&m,T::get_modulo()).into_iter().map(|x|x.into()).collect()})}}pub mod subset_convolution{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::ops::{AddAssign,SubAssign,MulAssign,Mul};pub fn lower_moebius<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=n-1;while i>=p{if i&p>0{v[i]-=v[i^p];i-=1;}else{i-=p;}}}}pub fn lower_zeta<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=0;while i<n{if i&p==0{v[i^p]+=v[i];i+=1;}else{i+=p;}}}}pub fn upper_zeta<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=n-1;while i>=p{if i&p>0{v[i^p]+=v[i];i-=1;}else{i-=p;}}}}pub fn upper_moebius<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=0;while i<n{if i&p==0{v[i]-=v[i^p];i+=1;}else{i+=p;}}}}pub fn subset_convolution<T:AddAssign+SubAssign+MulAssign+Mul<Output=T>+Default+Copy>(n:usize,a:&[T],b:&[T])->Vec<T>{let mut rank_a=vec![vec![Default::default();1<<n];n+1];let mut rank_b=vec![vec![Default::default();1<<n];n+1];for i in 0..(1<<n)as usize{rank_a[i.count_ones()as usize][i]=a[i];rank_b[i.count_ones()as usize][i]=b[i];}for i in 0..=n{lower_zeta(&mut rank_a[i]);lower_zeta(&mut rank_b[i]);}for i in(0..=n).rev(){rank_a[i].iter_mut().zip(rank_b[0].iter()).for_each(|(x,y)|*x*=*y);let(rank_a,ri)=rank_a.split_at_mut(i);for j in 1..=i{ri[0].iter_mut().zip(rank_a[i-j].iter().zip(rank_b[j].iter())).for_each(|(x,(y,z))|*x+=*y**z);}}for i in 0..=n{lower_moebius(&mut rank_a[i]);}let mut res=Vec::with_capacity(1<<n);for i in 0..(1<<n)as usize{res.push(rank_a[i.count_ones()as usize][i]);}res}}pub mod divisor_zeta{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};pub fn lower_divisor_zeta<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1){s[k]=true;v[k]+=v[j];}}}}pub fn lower_divisor_moebius<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1).rev(){s[k]=true;v[k]-=v[j];}}}}pub fn upper_divisor_zeta<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1).rev(){s[k]=true;v[j]+=v[k];}}}}pub fn upper_divisor_moebius<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1){s[k]=true;v[j]-=v[k];}}}}}}}
        pub mod minimal_lib_poly {use crate::__cargo_equip::preludes::minimal_lib_poly::*;pub mod misc{use crate::__cargo_equip::preludes::minimal_lib_poly::*;pub trait Composite<Rhs>{type Output;fn composite(&self,rhs:Rhs)->Self::Output;}}pub mod poly{use crate::__cargo_equip::preludes::minimal_lib_poly::*;pub mod boston_mori{use crate::__cargo_equip::preludes::minimal_lib_poly::*;use minimal_lib_int::modulo::{ModInt,Modulus};use super::Polynomial;fn altarnate<T:Modulus>(p:&Polynomial<T>)->Polynomial<T>{let mut pr:Polynomial<T> =p.clone();for x in pr.v.iter_mut().skip(1).step_by(2){*x=-*x;}pr}pub(in crate::__cargo_equip::crates::minimal_lib_poly)fn even<T:Modulus>(p:&mut Polynomial<T>){let n=p.n;for(j,i)in(0..=n).step_by(2).enumerate(){p.v[j]=p.v[i];}p.v.truncate(n/2+1);p.n=p.v.len()-1;}pub(in crate::__cargo_equip::crates::minimal_lib_poly)fn odd<T:Modulus>(p:&mut Polynomial<T>){let n=p.n;for(j,i)in(1..=n).step_by(2).enumerate(){p.v[j]=p.v[i];}p.v.truncate((n+1)/2);p.n=p.v.len()-1;}pub fn boston_mori<T:Modulus>(p:&Polynomial<T>,q:&Polynomial<T>,n:usize)->ModInt<T>{if n==0{return p.v[0]/q.v[0];}let aq=altarnate(q);let mut v=q*&aq;even(&mut v);let mut u=p*&aq;if(n&1)==0{even(&mut u)}else{odd(&mut u)};boston_mori(&u,&v,n>>1)}}pub mod gcd{use crate::__cargo_equip::preludes::minimal_lib_poly::*;use super::Polynomial;use minimal_lib_int::modulo::{ModInt,Modulus};pub fn ex_euclid(a:i64,b:i64)->(i64,i64,i64){let mut a=a;let mut b=b;let mut c=1;let mut d=0;let mut e=0;let mut f=1;while a!=0{let q=b/a;let res=(b%a,a,d,c-d*q,f,e-f*q);a=res.0;b=res.1;c=res.2;d=res.3;e=res.4;f=res.5;}if b<0{e=-e;c=-c;b=-b;}(e,c,b)}#[derive(Debug)]struct GCDMatrix<T:Modulus>{a:Polynomial<T>,b:Polynomial<T>,c:Polynomial<T>,d:Polynomial<T>,}impl<T:Modulus>GCDMatrix<T>{fn new()->Self{Self{a:Polynomial::one(),b:Polynomial::zero(),c:Polynomial::zero(),d:Polynomial::one(),}}fn add_q(&mut self,q:Polynomial<T>){std::mem::swap(&mut self.a,&mut self.c);std::mem::swap(&mut self.b,&mut self.d);self.c-=&self.a*&q;self.d-=&self.b*&q;self.c.truncate_zero();self.d.truncate_zero();}fn const_mul(&mut self,q:ModInt<T>){self.a*=q;self.b*=q;}fn assert(&self){assert_eq!(self.a.v.len()-1,self.a.n);assert_eq!(self.b.v.len()-1,self.b.n);assert_eq!(self.c.v.len()-1,self.c.n);assert_eq!(self.d.v.len()-1,self.d.n);}fn mat_mul_left(&mut self,rhs:&GCDMatrix<T>){let mut a=&rhs.a*&self.a;a+=&rhs.b*&self.c;let mut b=&rhs.a*&self.b;b+=&rhs.b*&self.d;let mut c=&rhs.c*&self.a;c+=&rhs.d*&self.c;let mut d=&rhs.c*&self.b;d+=&rhs.d*&self.d;a.truncate_zero();b.truncate_zero();c.truncate_zero();d.truncate_zero();self.a=a;self.b=b;self.c=c;self.d=d;}fn vec_mul(&self,a:&Polynomial<T>,b:&Polynomial<T>)->(Polynomial<T>,Polynomial<T>){(&self.a*a+&self.b*b,&self.c*a+&self.d*b)}}fn half_gcd_inner<T:Modulus>(a:&mut Polynomial<T>,b:&mut Polynomial<T>,mat:&mut GCDMatrix<T>,){let n=a.degree()+1;let bn=b.degree()+1;let k=(n+1)/2;if bn<=k{return;}{let mut local_mat=GCDMatrix::new();let mut ah=a.upper_part(k);let mut bh=b.upper_part(k);half_gcd_inner(&mut ah,&mut bh,&mut local_mat);let(a2,b2)=local_mat.vec_mul(a,b);mat.mat_mul_left(&local_mat);*a=a2;*b=b2;a.truncate_zero();b.truncate_zero();}{let n=a.degree()+1;let bn=b.degree()+1;let k=(n+1)/2;if bn<=k{return;}let(mut q,mut r)=a.divmod(b);q.truncate_zero();r.truncate_zero();std::mem::swap(a,b);*b=r;mat.add_q(q);}if!b.is_zero(){let an2=a.degree()+1;let bn2=b.degree()+1;if bn2<=(an2+1)/2{return;}let mut local_mat=GCDMatrix::new();let mut ah=a.upper_part(2*k-(an2-1));let mut bh=b.upper_part(2*k-(an2-1));half_gcd_inner(&mut ah,&mut bh,&mut local_mat);let(a2,b2)=local_mat.vec_mul(a,b);mat.mat_mul_left(&local_mat);*a=a2;*b=b2;a.truncate_zero();b.truncate_zero();}}fn half_gcd<T:Modulus>(a:&Polynomial<T>,b:&Polynomial<T>)->(Polynomial<T>,GCDMatrix<T>){let mut a:Polynomial<T> =a.clone();let mut b:Polynomial<T> =b.clone();let mut mat=GCDMatrix::new();while!b.is_zero(){half_gcd_inner(&mut a,&mut b,&mut mat);let(mut q,mut r)=a.divmod(&b);q.truncate_zero();r.truncate_zero();a=b;b=r;mat.add_q(q);}a.truncate_zero();(a,mat)}pub fn gcd_and_inverse<T:Modulus>(f:&Polynomial<T>,g:&Polynomial<T>,)->(Polynomial<T>,Option<Polynomial<T>>){let mut b=g.clone();let mut an=f.degree();let mut bn=g.degree();let mut a=if an>bn{f.divmod(g).1}else{f.clone()};std::mem::swap(&mut a,&mut b);std::mem::swap(&mut an,&mut bn);let(a,mut mat)=half_gcd(&a,&b);if a.n==0{let d=a.v[0].inv();mat.b.truncate_zero();let z=mat.b.divmod(g).1;let mut inverse=z;inverse.truncate_zero();inverse*=d;return(a,Some(inverse));}(a,None)}pub fn inverse<T:Modulus>(f:&Polynomial<T>,g:&Polynomial<T>)->Option<Polynomial<T>>{gcd_and_inverse(f,g).1}}pub mod middle_euclid{use crate::__cargo_equip::preludes::minimal_lib_poly::*;use super::Polynomial;use minimal_lib_int::modulo::{ModInt,Modulus};pub fn ex_euclid(a:i64,b:i64)->(i64,i64,i64){let mut a=a;let mut b=b;let mut c=1;let mut d=0;let mut e=0;let mut f=1;while a!=0{let q=b/a;let res=(b%a,a,d,c-d*q,f,e-f*q);a=res.0;b=res.1;c=res.2;d=res.3;e=res.4;f=res.5;}if b<0{e=-e;c=-c;b=-b;}(e,c,b)}#[derive(Debug)]struct GCDMatrix<T:Modulus>{a:Polynomial<T>,b:Polynomial<T>,c:Polynomial<T>,d:Polynomial<T>,q:Vec<Polynomial<T>>,}impl<T:Modulus>GCDMatrix<T>{fn new()->Self{Self{a:Polynomial::one(),b:Polynomial::zero(),c:Polynomial::zero(),d:Polynomial::one(),q:Vec::new(),}}fn add_q(&mut self,q:Polynomial<T>){std::mem::swap(&mut self.a,&mut self.c);std::mem::swap(&mut self.b,&mut self.d);self.c-=&self.a*&q;self.d-=&self.b*&q;self.c.truncate_zero();self.d.truncate_zero();self.q.push(q);}fn const_mul(&mut self,q:ModInt<T>){self.a*=q;self.b*=q;}fn assert(&self){assert_eq!(self.a.v.len()-1,self.a.n);assert_eq!(self.b.v.len()-1,self.b.n);assert_eq!(self.c.v.len()-1,self.c.n);assert_eq!(self.d.v.len()-1,self.d.n);}fn mat_mul_left(&mut self,rhs:GCDMatrix<T>){let mut a=&rhs.a*&self.a;a+=&rhs.b*&self.c;let mut b=&rhs.a*&self.b;b+=&rhs.b*&self.d;let mut c=&rhs.c*&self.a;c+=&rhs.d*&self.c;let mut d=&rhs.c*&self.b;d+=&rhs.d*&self.d;a.truncate_zero();b.truncate_zero();c.truncate_zero();d.truncate_zero();self.a=a;self.b=b;self.c=c;self.d=d;for item in rhs.q.into_iter(){self.q.push(item);}}fn vec_mul(&self,a:&Polynomial<T>,b:&Polynomial<T>)->(Polynomial<T>,Polynomial<T>){(&self.a*a+&self.b*b,&self.c*a+&self.d*b)}}fn half_gcd_inner<T:Modulus>(a:&mut Polynomial<T>,b:&mut Polynomial<T>,mat:&mut GCDMatrix<T>,_n:usize,){let n=a.degree()+1;let bn=b.degree()+1;let k=(n+1)/2;if bn<=k{return;}{let mut local_mat=GCDMatrix::new();let mut ah=a.upper_part(k);let mut bh=b.upper_part(k);half_gcd_inner(&mut ah,&mut bh,&mut local_mat,n-k);let(a2,b2)=local_mat.vec_mul(a,b);mat.mat_mul_left(local_mat);*a=a2;*b=b2;a.truncate_zero();b.truncate_zero();}{let bn=b.degree()+1;if bn<=n{return;}let(mut q,mut r)=a.divmod(b);q.truncate_zero();r.truncate_zero();std::mem::swap(a,b);*b=r;mat.add_q(q);}if!b.is_zero(){let an2=a.degree()+1;let bn2=b.degree()+1;if bn2<=(an2+1)/2{return;}let mut local_mat=GCDMatrix::new();let shift=2*k-(an2-1);let mut ah=a.upper_part(shift);let mut bh=b.upper_part(shift);half_gcd_inner(&mut ah,&mut bh,&mut local_mat,n-shift);let(a2,b2)=local_mat.vec_mul(a,b);mat.mat_mul_left(local_mat);*a=a2;*b=b2;a.truncate_zero();b.truncate_zero();}}fn half_gcd<T:Modulus>(a:&Polynomial<T>,b:&Polynomial<T>,n:usize,)->(Polynomial<T>,GCDMatrix<T>){let mut a:Polynomial<T> =a.clone();let mut b:Polynomial<T> =b.clone();let mut mat=GCDMatrix::new();while b.degree()>mat.d.degree(){let d=b.degree();half_gcd_inner(&mut a,&mut b,&mut mat,d-n);if b.degree()<=mat.d.degree(){break;}let(mut q,mut r)=a.divmod(&b);q.truncate_zero();r.truncate_zero();a=b;b=r;mat.add_q(q);}(b,mat)}pub fn berlekamp_massey<T:Modulus>(f:&Polynomial<T>)->(Polynomial<T>,Polynomial<T>){let n=f.n;let mut bv=vec![0;n+2];bv[n+1]=1;let b=Polynomial::new(&bv);let(mut p,mut mat)=half_gcd(&b,f,n/2);mat.d.truncate_zero();let di=mat.d.v[0].inv();let mut q=mat.d;p*=di;q*=di;(p,q)}}pub mod multipoint{use crate::__cargo_equip::preludes::minimal_lib_poly::*;fn minimum_exponent(n:i64)->usize{(64-n.saturating_sub(1).leading_zeros())as _}use minimal_lib_int::{modulo::{ModInt,Modulus},utils::isqrt,};use super::{poly::Polynomial,shift::shift_evaluation};pub fn product_of_polys<T:Modulus>(poly:&[Polynomial<T>])->Polynomial<T>{let n=poly.len();let l=minimum_exponent(n as _);let mut sub=vec![Polynomial::one();1<<(l+1)];let i_base=(1<<l)-1;for i in 0..n{sub[i_base+i]=poly[i].clone();}for level in(0..l).rev(){let i_base=(1<<level)-1;for i in 0..(1<<level){let node=i_base+i;sub[node]=&sub[node*2+1]*&sub[node*2+2];}}sub.into_iter().next().unwrap()}pub fn multipoint_eval<T:Modulus>(poly:&Polynomial<T>,points:&[ModInt<T>])->Vec<ModInt<T>>{let n=points.len();let l=minimum_exponent(n as _);let mut sub=vec![Polynomial::one();1<<(l+1)];let mut rem=vec![Polynomial::one();1<<(l+1)];let i_base=(1<<l)-1;for i in 0..n{sub[i_base+i]=Polynomial::new(&[-points[i],ModInt::one()]);}for level in(0..l).rev(){let i_base=(1<<level)-1;for i in 0..(1<<level){let node=i_base+i;sub[node]=&sub[node*2+1]*&sub[node*2+2];}}rem[0]=poly%&sub[0];for i in 1..(1<<(l+1)){rem[i]=&rem[(i-1)>>1]%&sub[i];}let mut res=vec![];for i in 0..n{res.push(rem[i_base+i].raw_coeffs()[0]);}res}pub fn interpolate<T:Modulus>(xs:&[ModInt<T>],ys:&[ModInt<T>])->Polynomial<T>{let n=xs.len();let l=minimum_exponent(n as _);let mut mul=vec![Polynomial::one();1<<(l+1)];let mut sub=vec![Polynomial::one();1<<(l+1)];let i_base=(1<<l)-1;for i in 0..n{mul[i_base+i]=Polynomial::new(&[-xs[i],ModInt::one()]);}for level in(0..l).rev(){let i_base=(1<<level)-1;for i in 0..(1<<level){let node=i_base+i;mul[node]=&mul[node*2+1]*&mul[node*2+2];}}let w=mul[0].derivative();sub[0]=w;for i in 1..(1<<(l+1)){sub[i]=&sub[(i-1)>>1]%&mul[i];}for i in 0..n{sub[i_base+i]=Polynomial::new(&[ys[i]*sub[i_base+i].v[0].inv()]);}for level in(0..l).rev(){let i_base=(1<<level)-1;for i in 0..(1<<level){let node=i_base+i;sub[node]=&mul[node*2+1]*&sub[node*2+2]+&sub[node*2+1]*&mul[node*2+2];}}sub.into_iter().next().unwrap()}pub fn partial_fraction<T:Modulus>(f:&Polynomial<T>,xs:&[ModInt<T>])->Vec<ModInt<T>>{let ys=multipoint_eval(f,xs);let gs:Vec<_> =xs.iter().map(|&x|Polynomial::new(&[-x,ModInt::one()])).collect();let g=product_of_polys(&gs).derivative();let zs=multipoint_eval(&g,xs);ys.into_iter().zip(zs.into_iter()).map(|(x,y)|x/y).collect()}pub fn multipoint_geometric<T:Modulus>(f:&Polynomial<T>,a:ModInt<T>,r:ModInt<T>,n:usize,)->Vec<ModInt<T>>{if r==ModInt::zero(){return(0..n).map(|i|if i==0{f.eval(a)}else{f.v[0]}).collect();}let fd=f.degree();let wilen=(fd+1).max(n);let n2=n+fd;let mut w=vec![ModInt::zero();n2];let mut wi=vec![ModInt::zero();wilen];let mut apow=vec![ModInt::zero();fd+1];{let mut ta=ModInt::one();let mut tb=ModInt::one();let mut tai=ModInt::one();let mut tbi=ModInt::one();let mut aa=ModInt::one();let ri=r.inv();for i in 0..n2{w[i]=ta;ta*=tb;tb*=r;if i<wilen{wi[i]=tai;tai*=tbi;tbi*=ri;}if i<=fd{apow[i]=aa;aa*=a;}}}let mut y:Vec<_> =f.raw_coeffs().iter().enumerate().map(|(i,&x)|x*apow[i]*wi[i]).collect();y.reverse();let convol=T::convolution(&w,&y);let mut result=Vec::with_capacity(n);for i in 0..n{result.push(convol[fd+i]*wi[i])}result}pub fn interpolate_geometric<T:Modulus>(_ys:&[ModInt<T>],_a:ModInt<T>,_r:ModInt<T>,)->Vec<ModInt<T>>{todo!();}pub fn shift_arith<T:Modulus>(n:usize,d:usize,a:usize,b:usize)->Vec<ModInt<T>>{let a=ModInt::from(a);let b=ModInt::from(b);let d=ModInt::from(d);let mut q=n;let mut digs=vec![];while q>1{digs.push(q&1);q>>=1;}let mut seq=vec![ModInt::one();q+1];for i in 0..=q{for j in 0..q{seq[i]*=a*i.into()+b+ModInt::from(j)*d;}}let da=d/a;for i in digs.into_iter().rev(){let n=seq.len().into();let mut ext=shift_evaluation(&seq,n,seq.len());let mul=shift_evaluation(&seq,da*(n-ModInt::one()),seq.len());let extmul=shift_evaluation(&seq,da*(n-ModInt::one())+n,seq.len());for(x,y)in ext.iter_mut().zip(extmul.into_iter()){*x*=y;}for(x,y)in seq.iter_mut().zip(mul.into_iter()){*x*=y;}seq.extend(ext);if i==1{let sq=seq.len();for j in 0..sq{seq[j]*=a*j.into()+b+ModInt::from(sq-2)*d;}}else{seq.pop();}}debug_assert_eq!(seq.len(),n+1);seq}pub fn factorial_large<T:Modulus>(n:usize)->ModInt<T>{let m=T::get_modulo()as usize;if n>=m{return ModInt::zero();}if n==0{return ModInt::one();}let sq=isqrt(n as i64)as usize;let seq=shift_arith(sq,1,sq,1);let mut t=ModInt::one();for x in seq.into_iter().take(sq){t*=x;}for i in(1+sq*sq)..=n{t*=ModInt::from(i);}t}}pub mod poly{use crate::__cargo_equip::preludes::minimal_lib_poly::*;use std::{fmt::Debug,ops::{Add,AddAssign,Div,Mul,MulAssign,Neg,Rem,Sub,SubAssign},};use minimal_lib_int::modulo::{ModInt,Modulus};#[derive(Clone)]pub struct Polynomial<T:Modulus>{pub v:Vec<ModInt<T>>,pub n:usize,}impl<T:Modulus>Default for Polynomial<T>{fn default()->Self{Self{v:vec![ModInt::zero()],n:0,}}}impl<T:Modulus>Debug for Polynomial<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{if self.v.len()!=self.n+1{f.write_fmt(format_args!("*broken n = {} vl = {}*",self.n,self.v.len()))?;}f.debug_list().entries(&self.v).finish()}}impl<T:Modulus>Polynomial<T>{pub fn new<S:Copy+Into<ModInt<T>>>(v:&[S])->Self{Self{v:v.iter().map(|&x|x.into()).collect(),n:v.len()-1,}}pub fn new_degs(v:&[(usize,i64)])->Self{let max_degree=v.iter().map(|(x,_)|*x).max().unwrap_or(0);let mut res=vec![0;max_degree+1];for&(deg,val)in v.iter(){res[deg]+=val;}Self::new(&res)}#[deprecated]pub fn new_modint(v:&[ModInt<T>])->Self{Self{v:v.to_vec(),n:v.len()-1,}}pub fn one()->Self{Self{v:vec![ModInt::new(1)],n:0,}}pub fn zero()->Self{Self{v:vec![ModInt::zero()],n:0,}}pub fn coeffs(&self)->Vec<i64>{self.v.iter().map(|&x|x.into()).collect()}pub fn raw_coeffs(&self)->Vec<ModInt<T>>{self.v.clone()}pub fn borrow_coeffs(&self)->&Vec<ModInt<T>>{&self.v}pub fn borrow_coeffs_mut(&mut self)->&mut Vec<ModInt<T>>{&mut self.v}pub fn degree(&self)->usize{self.n}pub fn eval(&self,x:ModInt<T>)->ModInt<T>{let mut t=ModInt::zero();let mut a=ModInt::new(1);for i in 0..=self.n{t+=a*self.v[i];a*=x;}t}pub fn is_zero(&self)->bool{self.n==0&&self.v[0]==ModInt::zero()}pub(in crate::__cargo_equip::crates::minimal_lib_poly)fn upper_part(&self,n:usize)->Self{if n>self.n{return Self::zero();}Self{v:self.v[n..].to_vec(),n:self.n-n,}}pub(in crate::__cargo_equip::crates::minimal_lib_poly)fn split_part(&self,n:usize)->(Self,Self){let mut v=self.v[0..=n.min(self.n)].to_vec();v.resize(n+1,ModInt::zero());let(vh,nh)=if self.n>n{(self.v[(n+1)..=self.n].to_vec(),self.n-n-1)}else{(vec![ModInt::zero()],0)};(Self{v,n},Self{v:vh,n:nh})}pub(in crate::__cargo_equip::crates::minimal_lib_poly)fn hensel_lifting(&self,n:usize)->Self{let a=self.v[0];let mut v=Self::new(&[a.inv()]);let mut i=1;while i<=n{let(h0,mut h1)=self.split_part(i-1);h1.truncate(i-1);let c=(&v*&h0).split_part(i-1).1;let mut b=-&v*(&v*&h1+c);b.truncate(i-1);v.v.extend(b.v);i*=2;v.n=i-1;}v.truncate(n);v}pub fn truncate_zero(&mut self){let mut msb=0;for i in(0..self.v.len()).rev(){if self.v[i]!=ModInt::zero(){msb=i;break;}}self.v.truncate(msb+1);self.n=msb;}pub fn truncate(&mut self,n:usize){self.v.resize(n+1,ModInt::zero());self.n=n;}pub fn truncate_max(&mut self,n:usize){if self.n>n{self.v.resize(n+1,ModInt::zero());self.n=n;}}pub fn cut(&self)->Self{let mut msb=0;for i in 0..self.v.len(){if self.v[i]!=ModInt::zero(){msb=i;}}self.split_part(msb).0}pub fn derivative(&self)->Self{let n=self.n;let mut v=vec![ModInt::zero();n+1];for i in 0..n{v[i]=self.v[i+1]*ModInt::new((i+1)as i64);}Self{v,n}}pub fn reverse(&self)->Self{let n=self.n;let mut v=vec![ModInt::zero();n+1];for i in 0..=self.n{v[n-i]=self.v[i];}Self{v,n}}pub fn divmod(&self,rhs:&Self)->(Self,Self){let n=self.n;let m=rhs.n;if n<m{(Self::new(&[0]),self.clone())}else{let q=((self.reverse()*rhs.reverse().hensel_lifting(n-m)).split_part(n-m).0).reverse();let r=self-&(rhs*&q);(q,r.cut())}}pub fn gcd(&self,_rhs:Self)->(Self,Self){todo!()}pub fn from_segment_values(_first_x:i64,_values:&[i64])->Self{todo!()}pub fn shift(&self,v:usize)->Self{let mut res=vec![ModInt::zero();self.v.len()+v];res[v..].clone_from_slice(&self.v);Self{v:res,n:self.n+v,}}pub fn pow(&self,rhs:i64)->Self{let mut res=Self::one();let mut r=rhs;let mut a:Polynomial<T> =self.clone();while r>0{if r&1==1{res*=&a;}a=&a*&a;r>>=1;}res}pub fn powtrun(&self,rhs:i64,m:usize)->Self{let mut res=Self::one();let mut r=rhs;let mut a=self.clone();while r>0{if r&1==1{res=&res*&a;if res.n>m{res.truncate(m);}}a=&a*&a;if a.n>m{a.truncate(m);}r>>=1;}res}}impl<T:Modulus>Add for Polynomial<T>{type Output=Self;fn add(self,rhs:Self)->Self::Output{&self+&rhs}}impl<T:Modulus>Sub for Polynomial<T>{type Output=Self;fn sub(self,rhs:Self)->Self::Output{&self-&rhs}}impl<T:Modulus>Mul for Polynomial<T>{type Output=Self;fn mul(self,rhs:Self)->Self::Output{&self*&rhs}}impl<T:Modulus>Mul<ModInt<T>>for Polynomial<T>{type Output=Self;fn mul(self,rhs:ModInt<T>)->Self::Output{let r:Vec<ModInt<T>> =self.v.iter().map(|x|*x*rhs).collect();Polynomial::new(&r)}}impl<T:Modulus>Div<ModInt<T>>for Polynomial<T>{type Output=Self;fn div(self,rhs:ModInt<T>)->Self::Output{let irhs=rhs.inv();let r:Vec<ModInt<T>> =self.v.iter().map(|x|*x*irhs).collect();Polynomial::new(&r)}}impl<T:Modulus>Neg for Polynomial<T>{type Output=Self;fn neg(self)->Self::Output{-&self}}impl<T:Modulus>Add for&Polynomial<T>{type Output=Polynomial<T>;fn add(self,rhs:Self)->Self::Output{let max_n=self.n.max(rhs.n);let mut res_v=vec![ModInt::zero();max_n+1];for i in 0..=self.n{res_v[i]+=self.v[i];}for i in 0..=rhs.n{res_v[i]+=rhs.v[i];}Polynomial{n:max_n,v:res_v}}}impl<T:Modulus>Sub for&Polynomial<T>{type Output=Polynomial<T>;fn sub(self,rhs:Self)->Self::Output{let max_n=self.n.max(rhs.n);let mut res_v=vec![ModInt::zero();max_n+1];for i in 0..=self.n{res_v[i]+=self.v[i];}for i in 0..=rhs.n{res_v[i]-=rhs.v[i];}Polynomial{n:max_n,v:res_v}}}impl<T:Modulus>AddAssign for Polynomial<T>{fn add_assign(&mut self,rhs:Self){let max_n=self.n.max(rhs.n);self.v.resize(max_n+1,ModInt::zero());self.n=max_n;for i in 0..=rhs.n{self.v[i]+=rhs.v[i];}}}impl<T:Modulus>AddAssign<&Polynomial<T>>for Polynomial<T>{fn add_assign(&mut self,rhs:&Self){let max_n=self.n.max(rhs.n);self.v.resize(max_n+1,ModInt::zero());self.n=max_n;for i in 0..=rhs.n{self.v[i]+=rhs.v[i];}}}impl<T:Modulus>SubAssign for Polynomial<T>{fn sub_assign(&mut self,rhs:Self){let max_n=self.n.max(rhs.n);self.v.resize(max_n+1,ModInt::zero());self.n=max_n;for i in 0..=rhs.n{self.v[i]-=rhs.v[i];}}}impl<T:Modulus>SubAssign<&Polynomial<T>>for Polynomial<T>{fn sub_assign(&mut self,rhs:&Self){let max_n=self.n.max(rhs.n);self.v.resize(max_n+1,ModInt::zero());self.n=max_n;for i in 0..=rhs.n{self.v[i]-=rhs.v[i];}}}impl<T:Modulus>MulAssign<ModInt<T>>for Polynomial<T>{fn mul_assign(&mut self,rhs:ModInt<T>){self.v.iter_mut().for_each(|x|*x*=rhs);}}impl<T:Modulus>MulAssign<&Polynomial<T>>for Polynomial<T>{fn mul_assign(&mut self,rhs:&Self){let v=T::convolution(&self.v,&rhs.v);self.n+=rhs.n;self.v=v;}}impl<T:Modulus>Mul for&Polynomial<T>{type Output=Polynomial<T>;fn mul(self,rhs:&Polynomial<T>)->Self::Output{let n=self.n+rhs.n;Polynomial{n,v:T::convolution(&self.v,&rhs.v),}}}impl<T:Modulus>Rem for&Polynomial<T>{type Output=Polynomial<T>;fn rem(self,rhs:&Polynomial<T>)->Self::Output{let(_,m)=self.divmod(rhs);m}}impl<T:Modulus>Neg for&Polynomial<T>{type Output=Polynomial<T>;fn neg(self)->Self::Output{let n=self.n;let v=self.v.iter().map(|&x|-x).collect();Polynomial{v,n}}}}pub mod shift{use crate::__cargo_equip::preludes::minimal_lib_poly::*;use minimal_lib_int::modulo::{ModInt,Modulus};fn point_to_descend<T:Modulus>(xs:&[ModInt<T>])->Vec<ModInt<T>>{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum_inv=&cache.accum_inv;let n=xs.len();let mut x:Vec<ModInt<T>> =Vec::with_capacity(n);let mut y:Vec<ModInt<T>> =Vec::with_capacity(n);for(i,xs)in xs.iter().enumerate(){if i&1==0{x.push(*xs*accum_inv[i].into());y.push(accum_inv[i].into());}else{let s=*xs*accum_inv[i].into();let t=(-accum_inv[i]).into();x.push(s);y.push(t);}}let mut z=T::convolution(&x,&y);z.truncate(n);z})}fn descend_to_point<T:Modulus>(xs:&[ModInt<T>])->Vec<ModInt<T>>{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum=&cache.accum;let accum_inv=&cache.accum_inv;let n=xs.len();let mut x=Vec::with_capacity(n);let mut y=Vec::with_capacity(n);for(i,xs)in xs.iter().enumerate(){x.push(*xs);y.push(accum_inv[i].into());}let mut z=T::convolution(&x,&y);z.truncate(n);for(i,z)in z.iter_mut().enumerate(){*z*=accum[i].into();}z})}pub fn shift_evaluation_single<T:Modulus>(xs:&[ModInt<T>],c:ModInt<T>)->ModInt<T>{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum_inv=&cache.accum_inv;let n=xs.len();let mut l=vec![ModInt::zero();n];let mut r=vec![ModInt::zero();n];l[0]=ModInt::one();r[n-1]=ModInt::one();for i in 1..n{let j=n-i-1;l[i]=l[i-1]*(c-((i-1)as i64).into());r[j]=r[j+1]*(c-((j+1)as i64).into());}let mut t=ModInt::zero();for(i,((&l,&r),(&a,&ai)))in l.iter().zip(r.iter()).zip(accum_inv.iter().zip(accum_inv.iter().rev())).enumerate(){let mut v=l*r*ModInt::from(a*ai);if(n-i-1)&1>0{v=-v;}t+=v*xs[i];}t})}pub fn shift_evaluation<T:Modulus>(xs:&[ModInt<T>],c:ModInt<T>,m:usize)->Vec<ModInt<T>>{if m==1{return vec![shift_evaluation_single(xs,c)];}T::mul_cache().with(|cache|{let cache=cache.borrow();let accum=&cache.accum;let accum_inv=&cache.accum_inv;let n=xs.len();let mut xs=point_to_descend(xs);xs.iter_mut().enumerate().for_each(|(i,x)|{*x*=ModInt::new(accum[i]);});let mut ys=vec![ModInt::zero();n];let mut cur=ModInt::new(1);ys.iter_mut().rev().zip(accum_inv.iter().enumerate()).for_each(|(y,(i,&ac))|{*y=cur*ac.into();cur*=c-ModInt::new(i as i64);});let mut zs=T::convolution(&xs,&ys);for i in 0..n{zs[i]=zs[i+n-1]*accum_inv[i].into();}zs.resize(m,ModInt::zero());if n<m{zs[n..m].fill(ModInt::zero());}descend_to_point(&zs)})}}pub use gcd::inverse;pub use poly::Polynomial;}pub use poly::Polynomial;}
    }

    pub(crate) mod macros {
        pub mod minimal_lib_algo {}
        pub mod minimal_lib_int {}
        pub mod minimal_lib_poly {}
    }

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

    mod preludes {
        pub mod minimal_lib_algo {}
        pub mod minimal_lib_int {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::minimal_lib_algo;}
        pub mod minimal_lib_poly {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::minimal_lib_int;}
    }
}
0