結果

問題 No.2762 Counting and Deleting
ユーザー 37kt37kt
提出日時 2024-06-11 11:12:11
言語 Rust
(1.77.0)
結果
AC  
実行時間 338 ms / 4,000 ms
コード長 26,387 bytes
コンパイル時間 16,120 ms
コンパイル使用メモリ 379,128 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-06-11 11:12:33
合計ジャッジ時間 21,277 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 327 ms
15,872 KB
testcase_08 AC 324 ms
15,872 KB
testcase_09 AC 323 ms
15,872 KB
testcase_10 AC 322 ms
16,000 KB
testcase_11 AC 338 ms
15,872 KB
testcase_12 AC 334 ms
15,744 KB
testcase_13 AC 338 ms
15,744 KB
testcase_14 AC 323 ms
15,744 KB
testcase_15 AC 298 ms
15,872 KB
testcase_16 AC 298 ms
15,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use std::collections::BTreeSet;

use algebraic::{algebra, monoid};
use matrix::Matrix;
use modint::ModInt998244353 as Mint;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use segment_tree::SegmentTree;

algebra!(M, Matrix<Mint>);
monoid!(M, Matrix::e(3), |a, b| a * b);

fn main() {
    input! {
        n: usize,
        q: usize,
        s: Bytes,
    }
    let a = s
        .into_iter()
        .map(|x| {
            if x == b'0' {
                Matrix::from(vec![
                    vec![1.into(), 0.into(), 0.into()],
                    vec![1.into(), 1.into(), 0.into()],
                    vec![0.into(), 0.into(), 1.into()],
                ])
            } else {
                Matrix::from(vec![
                    vec![1.into(), 1.into(), 0.into()],
                    vec![0.into(), 1.into(), 0.into()],
                    vec![0.into(), 1.into(), 1.into()],
                ])
            }
        })
        .collect::<Vec<_>>();
    let mut seg = SegmentTree::<M>::from(a);
    let mut st = (0..n).collect::<BTreeSet<usize>>();
    for _ in 0..q {
        input! {
            t: usize,
            l: Usize1,
            r: usize,
        }
        if t == 1 {
            while let Some(&x) = st.range(l..r).next() {
                seg.set(
                    x,
                    Matrix::from(vec![
                        vec![1.into(), 0.into(), 0.into()],
                        vec![0.into(), 1.into(), 0.into()],
                        vec![0.into(), 0.into(), 1.into()],
                    ]),
                );
                st.remove(&x);
            }
        } else {
            let t = seg.prod(l..r);
            println!("{}", t[0][0] + t[0][1] - 1);
        }
    }
}

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

///  # Bundled libraries
/// 
///  - `algebraic 0.1.0 (path+████████████████████████████████████████████████████████)`            published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebraic`
///  - `matrix 0.1.0 (path+████████████████████████████████████████████████)`                       published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::matrix`
///  - `modint 0.1.0 (path+█████████████████████████████████████████████████████████)`              published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint`
///  - `segment-tree 0.1.0 (path+████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::segment_tree`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x:&Self::S)->Self::S;}pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar:ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip::crates::algebraic::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::algebraic::One for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);}
        pub mod matrix {use crate::__cargo_equip::preludes::matrix::*;use std::{fmt::{Debug,Display},ops::{Add,AddAssign,Div,DivAssign,Index,IndexMut,Mul,MulAssign,Neg,Sub,SubAssign},};use algebraic::{One,Zero};#[derive(Clone)]pub struct Matrix<T>where T:Clone,{n:usize,m:usize,v:Box<[T]>,}impl<T>From<Vec<Vec<T>>>for Matrix<T>where T:Clone,{fn from(v:Vec<Vec<T>>)->Self{let n=v.len();let m=v[0].len();assert!(v.iter().all(|x|x.len()==m));Self{n,m,v:v.into_iter().flatten().collect::<Vec<_>>().into_boxed_slice(),}}}impl<T>Debug for Matrix<T>where T:Clone+Debug,{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{for i in 0..self.n{for j in 0..self.m{write!(f,"{:?}{}",self[i][j],if j+1==self.m{if i+1==self.n{""}else{"\n"}}else{" "})?}}Ok(())}}impl<T>Display for Matrix<T>where T:Clone+Display,{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{for i in 0..self.n{for j in 0..self.m{write!(f,"{}{}",self[i][j],if j+1==self.m{if i+1==self.n{""}else{"\n"}}else{" "})?}}Ok(())}}impl<T>Index<usize>for Matrix<T>where T:Clone,{type Output=[T];fn index(&self,index:usize)->&Self::Output{&self.v[index*self.m..(index+1)*self.m]}}impl<T>IndexMut<usize>for Matrix<T>where T:Clone,{fn index_mut(&mut self,index:usize)->&mut Self::Output{&mut self.v[index*self.m..(index+1)*self.m]}}impl<T>Matrix<T>where T:Clone,{pub fn n(&self)->usize{self.n}pub fn m(&self)->usize{self.m}pub fn transpose(&self)->Self{let mut a=Self{n:self.m,m:self.n,v:self.v.clone(),};for i in 0..self.n{for j in 0..self.m{a[j][i]=self[i][j].clone();}}a}}impl<T>Matrix<T>where T:Zero+Clone,{pub fn zeros(n:usize,m:usize)->Self{Self{n,m,v:vec![T::zero();n*m].into_boxed_slice(),}}}impl<T>Matrix<T>where T:Zero+One+Clone,{pub fn e(n:usize)->Self{let mut a=Self::zeros(n,n);for i in 0..n{a[i][i]=T::one();}a}}impl<T>Matrix<T>where T:Zero+One+Clone+Add<Output=T>+Mul<Output=T>,{pub fn pow(&self,mut k:usize)->Self{assert!(self.n==self.m);let mut a=self.clone();let mut b=Self::e(self.n);while k>0{if k&1!=0{b*=&a;}a*=&a.clone();k>>=1;}b}}impl<T>Matrix<T>where T:Zero+One+Clone+Eq+Neg<Output=T>+Add<Output=T>+Sub<Output=T>+Mul<Output=T>+Div<Output=T>,{pub fn gauss_elimination(&self)->(Self,usize,Option<T>){let mut a=self.clone();let mut rank=0;let mut det=T::one();let one=T::one();let zero=T::zero();for j in 0..self.m{if let Some(i)=(rank..self.n).position(|i|a[i][j]!=zero){let i=i+rank;if rank<i{det=-det;let(x,y)=a.v.split_at_mut(i*self.m);x[rank*self.m..(rank+1)*self.m].swap_with_slice(&mut y[0..self.m]);}det=det*a[rank][j].clone();if a[rank][j]!=one{let coef=one.clone()/a[rank][j].clone();for k in j..self.m{a[rank][k]=a[rank][k].clone()*coef.clone();}}for i in 0..self.n{if i==rank{continue;}if a[i][j]!=zero{let coef=a[i][j].clone()/a[rank][j].clone();for k in j..self.m{a[i][k]=a[i][k].clone()-a[rank][k].clone()*coef.clone();}}}rank+=1;}else{det=zero.clone();}}(a,rank,Some(det))}pub fn inv(&self)->Option<Self>{assert!(self.n==self.m);let one=T::one();let mut a=Self::zeros(self.n,self.n*2);for i in 0..self.n{for j in 0..self.n{a[i][j]=self[i][j].clone();}a[i][self.n+i]=one.clone();}let(b,_,_)=a.gauss_elimination();if b[self.n-1][self.n-1]!=one{return None;}let mut c=Self::zeros(self.n,self.n);for i in 0..self.n{for j in 0..self.n{c[i][j]=b[i][self.n+j].clone();}}Some(c)}}impl<T>Neg for Matrix<T>where T:Clone+Neg<Output=T>,{type Output=Self;fn neg(mut self)->Self::Output{for x in self.v.as_mut(){*x=-x.clone();}self}}impl<T>Neg for&Matrix<T>where T:Clone+Neg<Output=T>,{type Output=Matrix<T>;fn neg(self)->Self::Output{-self.clone()}}impl<T>AddAssign<&Self>for Matrix<T>where T:Clone+Add<Output=T>,{fn add_assign(&mut self,rhs:&Self){assert!((self.n,self.m)==(rhs.n,rhs.m));for(x,y)in self.v.as_mut().iter_mut().zip(rhs.v.as_ref()){*x=x.clone()+y.clone();}}}impl<T>SubAssign<&Self>for Matrix<T>where T:Clone+Sub<Output=T>,{fn sub_assign(&mut self,rhs:&Self){assert!((self.n,self.m)==(rhs.n,rhs.m));for(x,y)in self.v.as_mut().iter_mut().zip(rhs.v.as_ref()){*x=x.clone()-y.clone();}}}impl<T>MulAssign<&Self>for Matrix<T>where T:Zero+Clone+Add<Output=T>+Mul<Output=T>,{fn mul_assign(&mut self,rhs:&Self){assert!(self.m==rhs.n);let mut a=Self::zeros(self.n,rhs.m);for i in 0..self.n{for k in 0..self.m{for j in 0..rhs.m{a[i][j]=a[i][j].clone()+self[i][k].clone()*rhs[k][j].clone();}}}*self=a;}}impl<T>MulAssign<T>for Matrix<T>where T:Zero+Clone+Mul<Output=T>,{fn mul_assign(&mut self,rhs:T){for x in self.v.as_mut(){*x=x.clone()*rhs.clone();}}}impl<T>DivAssign<T>for Matrix<T>where T:Zero+One+Clone+Mul<Output=T>+Div<Output=T>,{fn div_assign(&mut self,rhs:T){*self*=T::one()/rhs;}}impl<T>Add<Self>for&Matrix<T>where T:From<i64>+Clone+Add<Output=T>,{type Output=Matrix<T>;fn add(self,rhs:Self)->Self::Output{let mut a=self.clone();a+=rhs;a}}impl<T>Sub<Self>for&Matrix<T>where T:Clone+Sub<Output=T>,{type Output=Matrix<T>;fn sub(self,rhs:Self)->Self::Output{let mut a=self.clone();a-=rhs;a}}impl<T>Mul<Self>for&Matrix<T>where T:Zero+Clone+Add<Output=T>+Mul<Output=T>,{type Output=Matrix<T>;fn mul(self,rhs:Self)->Self::Output{let mut a=self.clone();a*=rhs;a}}}
        pub mod modint {use crate::__cargo_equip::preludes::modint::*;use std::{fmt,hash::Hash,iter::{Product,Sum},num::ParseIntError,ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},str::FromStr,sync::atomic::{self,AtomicU32,AtomicU64},};use algebraic::{One,Zero};#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct StaticModInt<const P:u32>(u32);#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct DynamicModInt(u32);pub type ModInt998244353=StaticModInt<998_244_353>;pub type ModInt1000000007=StaticModInt<1_000_000_007>;pub trait ModInt:Default+FromStr+From<i8>+From<i16>+From<i32>+From<i64>+From<i128>+From<isize>+From<u8>+From<u16>+From<u32>+From<u64>+From<u128>+From<usize>+Copy+Eq+Hash+fmt::Display+fmt::Debug+Neg<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign{fn modulus()->u32;fn raw(val:u32)->Self;fn val(self)->u32;fn inv(self)->Self;fn pow(self,k:usize)->Self;fn sqrt(self)->Option<Self>;}const fn mul(x:u32,y:u32,m:u32)->u32{(x as u64*y as u64%m as u64)as u32}const fn pow(x:u32,mut n:u32,m:u32)->u32{if m==1{return 0;}let mut r=1u64;let mut y=(x%m)as u64;while n!=0{if n&1!=0{r=r*y%m as u64;}y=y*y%m as u64;n>>=1;}r as u32}const fn is_prime(n:u32)->bool{match n{_ if n<=1=>return false,2|7|61=>return true,_ if n&1==0=>return false,_=>{}}let mut d=n-1;while d&1==0{d>>=1;}let a=[2,7,61];let mut i=0;while i<3{let mut t=d;let mut y=pow(a[i],t,n);while t!=n-1&&y!=1&&y!=n-1{y=(y as u64*y as u64%n as u64)as u32;t<<=1;}if y!=n-1&&t&1==0{return false;}i+=1;}true}const fn extgcd(mut a:u32,b:u32)->(u32,u32){a=a%b;if a==0{return(b,0);}let mut s=b as i64;let mut t=a as i64;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;let tmp=s;s=t;t=tmp;let tmp=m0;m0=m1;m1=tmp;}if m0<0{m0+=b as i64/s;}(s as u32,m0 as u32)}const fn primitive_root(m:u32)->u32{match m{2=>return 1,167_772_161=>return 3,469_762_049=>return 3,754_974_721=>return 11,998_244_353=>return 3,_=>{}}let mut divs=[0;20];divs[0]=2;let mut cnt=1;let mut x=(m-1)/2;while x%2==0{x/=2;}let mut i=3;while i<std::u32::MAX{if i as u64*i as u64>x as u64{break;}if x%i==0{divs[cnt]=i;cnt+=1;while x%i==0{x/=i;}}i+=2;}if x>1{divs[cnt]=x;cnt+=1;}let mut g=2;loop{let mut i=0;while i<cnt{if pow(g,(m-1)/divs[i],m)==1{break;}i+=1;}if i==cnt{break g;}g+=1;}}const fn ntt_info(m:u32,)->(u32,usize,[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],){let g=primitive_root(m);let rank2=(m-1).trailing_zeros()as usize;let mut root=[0;30];let mut iroot=[0;30];let mut rate2=[0;30];let mut irate2=[0;30];let mut rate3=[0;30];let mut irate3=[0;30];root[rank2]=pow(g,(m-1)>>rank2,m);iroot[rank2]=extgcd(root[rank2],m).1;let mut i=rank2;while i>0{i-=1;root[i]=mul(root[i+1],root[i+1],m);iroot[i]=mul(iroot[i+1],iroot[i+1],m);}let mut prod=1;let mut iprod=1;let mut i=0;while i+2<=rank2{rate2[i]=mul(root[i+2],prod,m);irate2[i]=mul(iroot[i+2],iprod,m);prod=mul(prod,iroot[i+2],m);iprod=mul(iprod,root[i+2],m);i+=1;}let mut prod=1;let mut iprod=1;let mut i=0;while i+3<=rank2{rate3[i]=mul(root[i+3],prod,m);irate3[i]=mul(iroot[i+3],iprod,m);prod=mul(prod,iroot[i+3],m);iprod=mul(iprod,root[i+3],m);i+=1;}(g,rank2,root,iroot,rate2,irate2,rate3,irate3)}fn rat_convert(x:u64,m:u64,d:u64)->Option<(u64,u64)>{let n=m/(2*d);if x<n&&1<d{return Some((x,1));}let mut l=(0,1);let mut r=(1,0);loop{let num=l.0+r.0;let den=l.1+r.1;let(i,q)=match(num*m).cmp(&(den*x)){std::cmp::Ordering::Less=>{let k=(x*l.1-m*l.0-1)/(m*r.0-x*r.1);l.0+=k*r.0;l.1+=k*r.1;l}std::cmp::Ordering::Equal=>return None,std::cmp::Ordering::Greater=>{let k=(m*r.0-x*r.1-1)/(x*l.1-m*l.0);r.0+=k*l.0;r.1+=k*l.1;r}};if q*x<i*m{continue;}let p=q*x-i*m;if p<n&&q<d{return Some((p,q));}}}impl<const P:u32>ModInt for StaticModInt<P>{#[inline(always)]fn modulus()->u32{P}#[inline]fn raw(val:u32)->Self{Self(val)}#[inline]fn val(self)->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k)}fn sqrt(self)->Option<Self>{self.sqrt()}}impl<const P:u32>StaticModInt<P>{#[inline]pub fn new<T:Into<StaticModInt<P>>>(x:T)->Self{x.into()}#[inline(always)]pub fn modulus()->u32{P}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self.0}#[inline]pub fn inv(self)->Self{assert_ne!(self.0,0);self.pow(P as usize-2)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::from(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val()<2{return Some(self);}else if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b+=1;}let mut e=(p-1).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m);while y.val()!=1{let mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}}impl ModInt for DynamicModInt{#[inline(always)]fn modulus()->u32{BARRETT.modulus()}#[inline]fn raw(val:u32)->Self{Self(val)}#[inline]fn val(self)->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k)}fn sqrt(self)->Option<Self>{self.sqrt()}}impl DynamicModInt{#[inline]pub fn new<T:Into<DynamicModInt>>(x:T)->Self{x.into()}#[inline(always)]pub fn modulus()->u32{BARRETT.modulus()}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self.0}#[inline]pub fn inv(self)->Self{let(g,x)=extgcd(self.0,Self::modulus());assert_eq!(g,1);Self(x)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::from(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val()<2{return Some(self);}else if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b+=1;}let mut e=(p-1).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m);while y.val()!=1{let mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}pub fn set_modulus(modulus:u32){BARRETT.set(modulus)}}struct Barrett{m:AtomicU32,im:AtomicU64,}impl Barrett{const fn new(m:u32)->Self{Self{m:AtomicU32::new(m),im:AtomicU64::new((!0/m as u64).wrapping_add(1)),}}#[inline]fn set(&self,m:u32){let im=(!0/m as u64).wrapping_add(1);self.m.store(m,atomic::Ordering::SeqCst);self.im.store(im,atomic::Ordering::SeqCst);}#[inline]fn modulus(&self)->u32{self.m.load(atomic::Ordering::SeqCst)}#[inline]fn mul(&self,a:u32,b:u32)->u32{let m=self.m.load(atomic::Ordering::SeqCst);let im=self.im.load(atomic::Ordering::SeqCst);let mut z=a as u64;z*=b as u64;let x=(((z as u128)*(im as u128))>>64)as u64;let mut v=z.wrapping_sub(x.wrapping_mul(m as u64))as u32;if m<=v{v=v.wrapping_add(m);}v}}static BARRETT:Barrett=Barrett::new(998_244_353);impl<const P:u32>FromStr for StaticModInt<P>{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl FromStr for DynamicModInt{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl<const P:u32>fmt::Display for StaticModInt<P>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}impl fmt::Display for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}impl<const P:u32>fmt::Debug for StaticModInt<P>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{if let Some((num,den))=rat_convert(self.0 as u64,P as u64,1025){write!(f,"{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else if let Some((num,den))=rat_convert((P-self.0)as u64,P as u64,1025){write!(f,"-{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else{write!(f,"{}",self.0)?;}Ok(())}}impl fmt::Debug for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}macro_rules!impl_from_integer{($(($t1:ty,$t2:ty)),*)=>{$(impl<const P:u32>From<$t1>for StaticModInt<P>{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(P as$t2)as u32)}}impl From<$t1>for DynamicModInt{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(Self::modulus()as$t2)as u32)}})*};}impl_from_integer!((i8,i32),(i16,i32),(i32,i32),(i64,i64),(isize,i64),(i128,i128),(u8,u32),(u16,u32),(u32,u32),(u64,u64),(usize,u64),(u128,u128));impl<const P:u32,T:Into<Self>>AddAssign<T>for StaticModInt<P>{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=P{self.0-=P;}}}impl<T:Into<Self>>AddAssign<T>for DynamicModInt{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if self.0>=Self::modulus(){self.0-=Self::modulus();}}}impl<const P:u32,T:Into<Self>>SubAssign<T>for StaticModInt<P>{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=P;}self.0-=rhs;}}impl<T:Into<Self>>SubAssign<T>for DynamicModInt{fn sub_assign(&mut self,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=Self::modulus();}self.0-=rhs;}}impl<const P:u32,T:Into<Self>>MulAssign<T>for StaticModInt<P>{fn mul_assign(&mut self,rhs:T){*self=Self((self.0 as u64*rhs.into().0 as u64%P as u64)as u32);}}impl<T:Into<Self>>MulAssign<T>for DynamicModInt{fn mul_assign(&mut self,rhs:T){*self=Self(BARRETT.mul(self.0,rhs.into().0));}}impl<const P:u32,T:Into<Self>>DivAssign<T>for StaticModInt<P>{fn div_assign(&mut self,rhs:T){*self*=rhs.into().inv()}}impl<T:Into<Self>>DivAssign<T>for DynamicModInt{fn div_assign(&mut self,rhs:T){*self=*self*rhs.into().inv()}}impl<const P:u32>Neg for StaticModInt<P>{type Output=Self;fn neg(self)->Self::Output{if self.0==0{Self(0)}else{Self(P-self.0)}}}impl Neg for DynamicModInt{type Output=Self;fn neg(self)->Self::Output{if self.0==0{Self(0)}else{Self(Self::modulus()-self.0)}}}impl<const P:u32>Neg for&StaticModInt<P>{type Output=StaticModInt<P>;fn neg(self)->Self::Output{if self.0==0{StaticModInt(0)}else{StaticModInt(P-self.0)}}}impl Neg for&DynamicModInt{type Output=DynamicModInt;fn neg(self)->Self::Output{if self.0==0{DynamicModInt(0)}else{DynamicModInt(DynamicModInt::modulus()-self.0)}}}macro_rules!impl_ops{($($trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl<const P:u32>$trait_assign<&StaticModInt<P>>for StaticModInt<P>{fn$fn_assign(&mut self,rhs:&StaticModInt<P>){self.$fn_assign(*rhs);}}impl<const P:u32,T:Into<StaticModInt<P>>>$trait<T>for StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl<const P:u32>$trait<&StaticModInt<P>>for StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P>)->Self::Output{self.$fn(*rhs)}}impl<const P:u32,T:Into<StaticModInt<P>>>$trait<T>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl<const P:u32>$trait<&StaticModInt<P>>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P>)->Self::Output{(*self).$fn(*rhs)}}impl$trait_assign<&DynamicModInt>for DynamicModInt{fn$fn_assign(&mut self,rhs:&DynamicModInt){self.$fn_assign(*rhs);}}impl<T:Into<DynamicModInt>>$trait<T>for DynamicModInt{type Output=DynamicModInt;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl$trait<&DynamicModInt>for DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:&DynamicModInt)->Self::Output{self.$fn(*rhs)}}impl<T:Into<DynamicModInt>>$trait<T>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl$trait<&DynamicModInt>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs:&DynamicModInt)->Self::Output{(*self).$fn(*rhs)}})*};}impl_ops!{Add,AddAssign,add,add_assign,Sub,SubAssign,sub,sub_assign,Mul,MulAssign,mul,mul_assign,Div,DivAssign,div,div_assign,}impl<const P:u32>Sum for StaticModInt<P>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}impl<const P:u32>Product for StaticModInt<P>{fn product<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}impl<'a,const P:u32>Sum<&'a Self>for StaticModInt<P>{fn sum<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::raw(0),|b,x|b+x)}}impl<'a,const P:u32>Product<&'a Self>for StaticModInt<P>{fn product<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::from(1),|b,x|b*x)}}impl<const P:u32>StaticModInt<P>{pub const G:u32=ntt_info(P).0;pub const RANK2:usize=ntt_info(P).1;pub const ROOT:[u32;30]=ntt_info(P).2;pub const IROOT:[u32;30]=ntt_info(P).3;pub const RATE2:[u32;30]=ntt_info(P).4;pub const IRATE2:[u32;30]=ntt_info(P).5;pub const RATE3:[u32;30]=ntt_info(P).6;pub const IRATE3:[u32;30]=ntt_info(P).7;pub const IS_NTT_FRIENDLY:bool=is_prime(P)&&Self::RANK2>=21;}impl<const P:u32>Zero for StaticModInt<P>{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl<const P:u32>One for StaticModInt<P>{fn one()->Self{Self::new(1)}fn is_one(&self)->bool{self==&Self::one()}}impl Zero for DynamicModInt{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl One for DynamicModInt{fn one()->Self{Self::new(1)}fn is_one(&self)->bool{self==&Self::one()}}}
        pub mod segment_tree {use crate::__cargo_equip::preludes::segment_tree::*;use std::ops::{Bound,RangeBounds};use algebraic::Monoid;#[derive(Clone)]pub struct SegmentTree<M>where M:Monoid,M::S:Clone,{n:usize,v:Vec<M::S>,}impl<M>SegmentTree<M>where M:Monoid,M::S:Clone,{pub fn new(n:usize)->Self{Self{n,v:vec![M::e();n*2],}}pub fn set(&mut self,mut k:usize,x:M::S){k+=self.n;self.v[k]=x;while k>1{k>>=1;self.v[k]=M::op(&self.v[k*2],&self.v[k*2+1]);}}pub fn get(&self,k:usize)->M::S{assert!(k<self.n);self.v[k+self.n].clone()}pub fn prod<R>(&self,range:R)->M::S where R:RangeBounds<usize>,{let mut l=match range.start_bound(){Bound::Excluded(&l)=>l+1,Bound::Included(&l)=>l,Bound::Unbounded=>0,};let mut r=match range.end_bound(){Bound::Excluded(&r)=>r,Bound::Included(&r)=>r+1,Bound::Unbounded=>self.n,};assert!(l<=r);assert!(r<=self.n);l+=self.n;r+=self.n;let mut sl=M::e();let mut sr=M::e();while l<r{if l&1!=0{sl=M::op(&sl,&self.v[l]);l+=1;}if r&1!=0{r-=1;sr=M::op(&self.v[r],&sr);}l>>=1;r>>=1;}M::op(&sl,&sr)}pub fn max_right<P>(&self,mut l:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(pred(&M::e()));if pred(&self.prod(l..)){return self.n;}l+=self.n;let mut s=M::e();loop{while l&1==0&&self.is_good_node(l>>1){l>>=1;}if!pred(&M::op(&s,&self.v[l])){while l<self.n{l<<=1;let t=M::op(&s,&self.v[l]);if pred(&t){s=t;l+=1;}}return l-self.n;}s=M::op(&s,&self.v[l]);l+=1;}}pub fn min_left<P>(&self,mut r:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(r<=self.n);assert!(pred(&M::e()));if pred(&self.prod(..r)){return 0;}r+=self.n;let mut s=M::e();loop{r-=1;while!self.is_good_node(r){r=r*2+1;}while r&1!=0&&self.is_good_node(r>>1){r>>=1;}if!pred(&M::op(&self.v[r],&s)){while r<self.n{r=r*2+1;let t=M::op(&self.v[r],&s);if pred(&t){s=t;r-=1;}}return r+1-self.n;}s=M::op(&self.v[r],&s);}}#[inline]fn is_good_node(&self,k:usize)->bool{if k>=self.n{true}else{let d=k.leading_zeros()-self.n.leading_zeros();self.n>>d!=k||self.n>>d<<d==self.n}}}impl<M>From<Vec<M::S>>for SegmentTree<M>where M:Monoid,M::S:Clone,{fn from(mut a:Vec<M::S>)->Self{let n=a.len();let mut v=vec![M::e();n];v.append(&mut a);for i in(1..n).rev(){v[i]=M::op(&v[i*2],&v[i*2+1]);}Self{n,v}}}}
    }

    pub(crate) mod macros {
        pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};}
        pub mod matrix {}
        pub mod modint {}
        pub mod segment_tree {}
    }

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

    mod preludes {
        pub mod algebraic {}
        pub mod matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
        pub mod modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
        pub mod segment_tree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
    }
}
0