結果

問題 No.2511 Mountain Sequence
ユーザー Lenqth
提出日時 2023-10-20 22:18:33
言語 Rust
(1.83.0 + proconio)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 50,809 bytes
コンパイル時間 14,399 ms
コンパイル使用メモリ 379,528 KB
最終ジャッジ日時 2024-09-20 19:39:14
合計ジャッジ時間 15,066 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error[E0659]: `proconio` is ambiguous
 --> src/main.rs:6:5
  |
6 |     proconio::input! {
  |     ^^^^^^^^ ambiguous name
  |
  = note: ambiguous because of a conflict between a name from a glob import and an outer scope during import or macro resolution
  = note: `proconio` could refer to a crate passed with `--extern`
  = help: use `::proconio` to refer to this crate unambiguously
note: `proconio` could also refer to the module imported here
 --> src/main.rs:1:9
  |
1 | pub use __cargo_equip::prelude::*;
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^
  = help: consider adding an explicit import of `proconio` to disambiguate
  = help: or use `crate::proconio` to refer to this module unambiguously

For more information about this error, try `rustc --explain E0659`.
error: could not compile `main` (bin "main") due to 1 previous error

ソースコード

diff #
プレゼンテーションモードにする

pub use __cargo_equip::prelude::*;
use minimal_lib_int::modulo::{Mod998244353, ModInt};
fn main() {
proconio::input! {
n: usize,
m: usize
}
let mut t: ModInt<Mod998244353> = ModInt::zero();
for k in 0..m {
if 2 * k < n - 1 {
continue;
}
t += ModInt::combin(2 * k, n - 1);
}
println!("{}", t);
}
// 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`
/// - `proconio 0.4.5 (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
///
/// - `proconio 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// The MIT License
/// Copyright 2019 (C) statiolake <statiolake@gmail.com>
///
/// 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 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<'a>(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 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.clone();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)]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};}mod gerner{use crate::__cargo_equip::preludes::minimal_lib_int::*;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_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};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=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,T::get_modulo()).unwrap().into
            ())}result})}}pub mod subset_convolution{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::ops::{AddAssign,SubAssign
            ,MulAssign,Mul};use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};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];}}}}}}}<hide>
pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]pub use crate::__cargo_equip::macros::proconio::*;pub mod
            marker{use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for
            Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}pub
            enum Bytes{}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap
            ().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(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<R:BufRead,S:Source<R>>(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 std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use super::Source;use
            crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use std::io::BufRead;pub struct LineSource<R:BufRead>{tokens:Tokens,reader
            :R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{tokens:"".to_owned().into(),reader,}}fn prepare(&mut self
            ){while self.tokens.is_empty(){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.tokens=line.into();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self
            )->Option<&str>{self.prepare();self.tokens.next_token()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.is_empty()}}use std::io
            ::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new
            (BufReader::new(s.as_bytes()))}}}pub mod once{use super::Source;use crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use
            std::io::BufRead;use std::marker::PhantomData;pub struct OnceSource<R:BufRead>{tokens:Tokens,_read:PhantomData<R>,}impl<R:BufRead
            >OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed
            to read from source; maybe an IO error.");OnceSource{tokens:context.into(),_read:PhantomData,}}}impl<R:BufRead>Source<R>for OnceSource<R
            >{fn next_token(&mut self)->Option<&str>{self.tokens.next_token()}fn is_empty(&mut self)->bool{self.tokens.is_empty()}}use std::io
            ::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new
            (BufReader::new(s.as_bytes()))}}}mod tokens{use std::{iter::Peekable,ptr::NonNull,str::SplitWhitespace};pub(super)struct Tokens{tokens
            :Peekable<SplitWhitespace<'static>>,_current_context:CurrentContext,}impl Tokens{pub(super)fn next_token(&mut self)->Option<&str>{self
            .tokens.next()}pub(super)fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}impl From<String>for Tokens{fn from(current_context
            :String)->Self{let current_context=CurrentContext::from(current_context);unsafe{let tokens=current_context.0.as_ref().split_whitespace
            ().peekable();Self{tokens,_current_context:current_context,}}}}unsafe impl Send for Tokens{}unsafe impl Sync for Tokens{}struct
            CurrentContext(NonNull<str>);impl From<String>for CurrentContext{fn from(s:String)->Self{let s=s.into_boxed_str();Self(NonNull::new(Box
            ::leak(s)).unwrap())}}impl Drop for CurrentContext{fn drop(&mut self){unsafe{Box::from_raw(self.0.as_mut())};}}}pub mod auto{#[cfg
            (debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as
            AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;#[allow(clippy::wrong_self_convention)]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<R:BufRead,S
            :Source<R>>Source<R>for&'_ 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<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}impl<T:FromStr>Readable for T
            where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(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::<T>(),err=e,),}}}}use
            crate::__cargo_equip::crates::proconio::source::{auto::AutoSource,line::LineSource};use std::io::{BufReader,Stdin};use std::sync
            ::OnceLock;use std::{io::{self,BufRead},sync::Mutex,};pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;pub
            enum StdinSource<R:BufRead>{Normal(AutoSource<R>),Interactive(LineSource<R>),Unknown(LineSource<R>),}impl<R:BufRead>source::Source<R>for
            StdinSource<R>{fn next_token(&mut self)->Option<&str>{match self{StdinSource::Normal(source)=>source.next_token(),StdinSource
            ::Interactive(source)=>source.next_token(),StdinSource::Unknown(source)=>source.next_token(),}}fn is_empty(&mut self)->bool{match
            self{StdinSource::Normal(source)=>source.is_empty(),StdinSource::Interactive(source)=>source.is_empty(),StdinSource::Unknown(source
            )=>source.is_empty(),}}}pub static STDIN_SOURCE:OnceLock<Mutex<StdinSource<BufReader<Stdin>>>> =OnceLock::new
            ();#[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
            .get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource::Normal($crate::__cargo_equip::crates
            ::proconio::source::auto::AutoSource::new(std::io::BufReader::new(std::io::stdin())),))}).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 ","
            <https://github.com/statiolake/proconio-rs/issues>."));$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_input_interactive{($($rest:tt)*)=>{let mut locked_stdin=$crate
            ::__cargo_equip::crates::proconio::STDIN_SOURCE.get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource
            ::Interactive($crate::__cargo_equip::crates::proconio::source::line::LineSource::new(std::io::BufReader::new(std::io::stdin())),))}).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 ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio
            ::input!{from&mut*locked_stdin,$($rest)*}drop(locked_stdin);};}macro_rules!input_interactive{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def_proconio_input_interactive!{$($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=<usize as$crate::__cargo_equip::crates::proconio::__Readable
            >::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
            ::<Vec<_>>()}};(@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 ","<https
            ://github.com/statiolake/proconio-rs/issues>."));};(@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 source::Source;let mut lock=STDIN_SOURCE.get_or_init(||{Mutex::new(StdinSource::Unknown(LineSource
            ::new(BufReader::new(io::stdin(),))))}).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 ","<https://github.com/statiolake/proconio-rs/issues>."
            ));lock.is_empty()}}<hide>
}
pub(crate) mod macros {
pub mod minimal_lib_algo {}
pub mod minimal_lib_int {}
pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_input_interactive as
            input_interactive,__cargo_equip_macro_def_proconio_read_value as read_value};}
}
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 proconio {}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0