// codesnip-guard: LcmConvolve
#[cfg_attr(any(),rustfmt::skip)]pub use self::lcm_convolve::LcmConvolve;#[cfg_attr(any(),rustfmt::skip)]mod lcm_convolve{use super::{ConvolveSteps,Group,Invertible,Monoid,Ring,with_prime_list};use std::marker::PhantomData;pub struct LcmConvolve<M>{_marker:PhantomData<fn()->M>}impl<M>LcmConvolve<M>where M:Monoid{#[doc=" $$g(m) = \\sum_{n \\mid m}f(n)$$"]pub fn zeta_transform(f:&mut[M::T]){let n=f.len().saturating_sub(1)as u32;with_prime_list(n,|pl|{for p in pl.primes_lte(n){for(i,j)in(0..f.len()).step_by(p as _).enumerate(){f[j]=M::operate(&f[j],&f[i]);}}})}}impl<G>LcmConvolve<G>where G:Group{#[doc=" $$f(m) = \\sum_{n \\mid m}h(n)$$"]pub fn mobius_transform(f:&mut[G::T]){let n=f.len().saturating_sub(1)as u32;with_prime_list(n,|pl|{for p in pl.primes_lte(n).rev(){(1..=(f.len()-1)/p as usize).rev().for_each(|i|{let j=i*p as usize;f[j]=G::rinv_operate(&f[j],&f[i]);});f[0]=G::rinv_operate(&f[0],&f[0]);}})}}impl<R>ConvolveSteps for LcmConvolve<R>where R:Ring<Additive:Invertible>{type T=Vec<R::T>;type F=Vec<R::T>;fn length(t:&Self::T)->usize{t.len()}fn transform(mut t:Self::T,_len:usize)->Self::F{LcmConvolve::<R::Additive>::zeta_transform(&mut t);t}fn inverse_transform(mut f:Self::F,_len:usize)->Self::T{LcmConvolve::<R::Additive>::mobius_transform(&mut f);f}fn multiply(f:&mut Self::F,g:&Self::F){for(f,g)in f.iter_mut().zip(g){*f=R::mul(f,g);}}}}
// codesnip-guard: AdditiveOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::additive_operation_impl::AdditiveOperation;#[cfg_attr(any(),rustfmt::skip)]mod additive_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Neg,Sub}};#[doc=" $+$"]pub struct AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()+y.clone()}}impl<T>Unital for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{#[inline]fn unit()->Self::T{Zero::zero()}}impl<T>Associative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Commutative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Invertible for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>+Sub<Output=T>+Neg<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{-x.clone()}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()-y.clone()}}}
// codesnip-guard: ConvolveSteps
#[cfg_attr(any(),rustfmt::skip)]pub use self::convolve_steps::ConvolveSteps;#[cfg_attr(any(),rustfmt::skip)]mod convolve_steps{pub trait ConvolveSteps{#[doc=" Whether transform multiplication computes modulo x^n - 1 in the coefficient ring."]const CYCLIC:bool=false;type T;type F;fn length(t:&Self::T)->usize;fn transform(t:Self::T,len:usize)->Self::F;fn inverse_transform(f:Self::F,len:usize)->Self::T;fn multiply(f:&mut Self::F,g:&Self::F);fn square(t:Self::T,len:usize)->Self::T where Self::T:Clone{let mut f=Self::transform(t.clone(),len);let g=Self::transform(t,len);Self::multiply(&mut f,&g);Self::inverse_transform(f,len)}fn convolve(a:Self::T,b:Self::T)->Self::T{let len=(Self::length(&a)+Self::length(&b)).saturating_sub(1);let mut a=Self::transform(a,len);let b=Self::transform(b,len);Self::multiply(&mut a,&b);Self::inverse_transform(a,len)}}}
// codesnip-guard: MultiplicativeOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::multiplicative_operation_impl::MultiplicativeOperation;#[cfg_attr(any(),rustfmt::skip)]mod multiplicative_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Div,Mul}};#[doc=" $\\times$"]pub struct MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()*y.clone()}}impl<T>Unital for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{#[inline]fn unit()->Self::T{One::one()}}impl<T>Associative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Commutative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Invertible for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>+Div<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{Self::unit().div(x.clone())}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{(x.clone()).div(y.clone())}}}
// codesnip-guard: PrimeList
#[cfg_attr(any(),rustfmt::skip)]pub use self::prime_list::{PrimeList,with_prime_list};#[cfg_attr(any(),rustfmt::skip)]mod prime_list{use std::{cell::UnsafeCell,mem::replace,ops::Range};const WHEEL_PRIMES:[u32;4]=[2,3,5,7];const PERIOD:u32=210;const COPRIME:usize=48;const SQRT_THRESHOLD:u32=1<<16;const fn coprime_to_wheel(x:u32)->bool{!x.is_multiple_of(2)&&!x.is_multiple_of(3)&&!x.is_multiple_of(5)&&!x.is_multiple_of(7)}const fn residues()->[u8;COPRIME]{let mut result=[0;COPRIME];let mut i=1;let mut j=0;while i<PERIOD{if coprime_to_wheel(i){result[j]=i as u8;j+=1;}i+=2;}result}const RESIDUES:[u8;COPRIME]=residues();const fn states()->[u8;PERIOD as usize]{let mut result=[0;PERIOD as usize];let mut i=0;let mut j=0;while i<PERIOD{result[i as usize]=j;if coprime_to_wheel(i){j+=1;}i+=1;}result}const STATES:[u8;PERIOD as usize]=states();const fn additions()->[u8;PERIOD as usize]{let mut result=[0;PERIOD as usize];let mut i=0;while i<PERIOD{let mut add=1;while!coprime_to_wheel(i+add){add+=1;}result[i as usize]=add as u8;i+=1;}result}const ADDITIONS:[u8;PERIOD as usize]=additions();const fn gaps()->[u8;COPRIME]{let mut result=[0;COPRIME];let mut i=0;while i<COPRIME{result[i]=ADDITIONS[RESIDUES[i]as usize];i+=1;}result}const GAPS:[u8;COPRIME]=gaps();const fn to_ordinal(x:u32)->u32{x/PERIOD*COPRIME as u32+STATES[(x%PERIOD)as usize]as u32}const fn to_value(x:u32)->u32{x/COPRIME as u32*PERIOD+RESIDUES[x as usize%COPRIME]as u32}const fn ordinal_to_value()->[u16;256]{let mut result=[0;256];let mut i=0;while i<result.len(){result[i]=to_value(i as u32)as u16;i+=1;}result}const ORDINAL_TO_VALUE:[u16;256]=ordinal_to_value();const fn sqrt_bits()->[u64;SQRT_THRESHOLD as usize/128]{let mut result=[!0;SQRT_THRESHOLD as usize/128];let ordinal=to_ordinal(1)as usize;result[ordinal/64]&=!(1<<(ordinal%64));let mut i=RESIDUES[1]as u32;while to_ordinal(i*i)<SQRT_THRESHOLD/2{let ordinal=to_ordinal(i)as usize;if result[ordinal/64]>>(ordinal%64)&1!=0{let mut k=i;while to_ordinal(i*k)<SQRT_THRESHOLD/2{let ordinal=to_ordinal(i*k)as usize;result[ordinal/64]&=!(1<<(ordinal%64));k+=ADDITIONS[(k%PERIOD)as usize]as u32;}}i+=ADDITIONS[(i%PERIOD)as usize]as u32;}result}const SQRT_BITS:[u64;SQRT_THRESHOLD as usize/128]=sqrt_bits();const fn count_sqrt_primes()->usize{let mut result=0;let mut i=RESIDUES[1]as u32;while i<SQRT_THRESHOLD{let ordinal=to_ordinal(i)as usize;result+=(SQRT_BITS[ordinal/64]>>(ordinal%64)&1)as usize;i+=ADDITIONS[(i%PERIOD)as usize]as u32;}result}const SQRT_PRIME_COUNT:usize=count_sqrt_primes();const fn sqrt_primes()->[u32;SQRT_PRIME_COUNT]{let mut result=[0;SQRT_PRIME_COUNT];let mut i=RESIDUES[1]as u32;let mut j=0;while i<SQRT_THRESHOLD{let ordinal=to_ordinal(i)as usize;if SQRT_BITS[ordinal/64]>>(ordinal%64)&1!=0{result[j]=i;j+=1;}i+=ADDITIONS[(i%PERIOD)as usize]as u32;}result}static SQRT_PRIMES:[u32;SQRT_PRIME_COUNT]=sqrt_primes();struct Wheel{mask:Vec<u64>,product:u32}impl Wheel{fn new(primes:&[u32],product:u32)->Self{let mut mask=vec![!0;to_ordinal(product)as usize/64];for&p in primes{let mut k=1;while p*k<product{let ordinal=to_ordinal(p*k)as usize;mask[ordinal/64]&=!(1<<(ordinal%64));k+=ADDITIONS[(k%PERIOD)as usize]as u32;}}Self{mask,product}}}fn make_wheels()->(Vec<Wheel>,usize){const MAX_WHEEL_SIZE:u32=1<<20;const BASE:u32=(PERIOD*64)>>(WHEEL_PRIMES.len()-2);let mut product=BASE;let mut current=vec![];let mut wheels=vec![];for(i,&p)in SQRT_PRIMES.iter().enumerate(){if product*p>MAX_WHEEL_SIZE{wheels.push(Wheel::new(&current,product));current.clear();current.push(p);product=BASE*p;if product>MAX_WHEEL_SIZE{return(wheels,i);}}else{current.push(p);product*=p;}}unreachable!()}fn sieve_dense(bits:&mut[u64],l:u32,r:u32,wheel:&Wheel){let mut left=l as usize/64;let right=(r as usize).div_ceil(64);while left+wheel.mask.len()<=right{for(value,&mask)in bits[left..left+wheel.mask.len()].iter_mut().zip(&wheel.mask){*value&=mask;}left+=wheel.mask.len();}for(value,&mask)in bits[left..right].iter_mut().zip(&wheel.mask){*value&=mask;}}fn ordinal_steps()->Vec<[u32;COPRIME*2]>{SQRT_PRIMES.iter().map(|&p|{let mut result=[0;COPRIME*2];let mut last=to_ordinal(p);for i in 0..COPRIME{let next=to_ordinal(p*(RESIDUES[i]as u32+GAPS[i]as u32));result[i]=next-last;result[i+COPRIME]=next-last;last=next;}result}).collect()}fn sieve_sparse(bits:&mut[u64],mut left:u32,right:u32,prime_index:usize,mut state:u8,steps:&[[u32;COPRIME*2]])->(u32,u8){let p=SQRT_PRIMES[prime_index];while left+p*COPRIME as u32<=right{for _ in 0..COPRIME{let ordinal=left as usize;bits[ordinal/64]&=!(1<<(ordinal%64));left+=steps[prime_index][state as usize];state+=1;}state-=COPRIME as u8;}while left<right{let ordinal=left as usize;bits[ordinal/64]&=!(1<<(ordinal%64));left+=steps[prime_index][state as usize];state+=1;}if state>=COPRIME as u8{state-=COPRIME as u8;}(left,state)}#[derive(Debug,Clone)]pub struct PrimeList{bits:Vec<u64>,bit_len:usize,max_n:u32,prime_count:usize}impl Default for PrimeList{fn default()->Self{Self{bits:vec![],bit_len:0,max_n:1,prime_count:0}}}impl PrimeList{pub fn new(max_n:u32)->Self{let mut self_:Self=Default::default();self_.reserve(max_n);self_}pub fn primes(&self)->PrimeListIter<'_>{self.primes_lte(self.max_n)}pub fn len(&self)->usize{self.prime_count}pub fn is_empty(&self)->bool{self.prime_count==0}pub fn primes_lte(&self,n:u32)->PrimeListIter<'_>{assert!(n<=self.max_n,"expected `n={} <= {}`",n,self.max_n);let bit_len=to_ordinal(n.saturating_add(1))as usize;let words=&self.bits[..self.bits.len().min(bit_len.div_ceil(64))];let last_mask=if bit_len.is_multiple_of(64){!0}else{(1<<(bit_len%64))-1};let(front_word,middle_words,back_word)=match words{[]=>(0,words,0),[word]=>(*word&last_mask,&words[1..],0),[front,middle@..,back]=>(*front,middle,*back&last_mask),};let back_word_ordinal=words.len().saturating_sub(1)as u32*64;PrimeListIter{wheel_indices:0..WHEEL_PRIMES.partition_point(|&p|p<=n)as u8,middle_words,front_word_base:0,front_word_phase:0,front_word,back_word_base:back_word_ordinal/COPRIME as u32*PERIOD,back_word_phase:(back_word_ordinal%COPRIME as u32)as u8,back_word}}pub fn is_prime(&self,n:u32)->bool{assert!(n<=self.max_n,"expected `n={} <= {}`",n,self.max_n);if WHEEL_PRIMES.contains(&n){true}else if!coprime_to_wheel(n){false}else{let ordinal=to_ordinal(n)as usize;ordinal<self.bit_len&&self.bits[ordinal/64]>>(ordinal%64)&1!=0}}pub fn trial_division(&self,n:u64)->PrimeListTrialDivision<'_>{let bound=u64::from(self.max_n).pow(2);assert!(n<=bound,"expected `n={} <= {}`",n,bound);PrimeListTrialDivision{primes:self.primes(),n}}pub fn prime_factors(&self,n:u64)->Vec<(u64,u32)>{self.trial_division(n).collect()}pub fn count_divisors(&self,n:u64)->u64{let mut divisor_cnt=1u64;for(_,cnt)in self.trial_division(n){divisor_cnt*=cnt as u64+1;}divisor_cnt}pub fn divisors(&self,n:u64)->Vec<u64>{let mut d=vec![1u64];for(p,c)in self.trial_division(n){let k=d.len();let mut acc=1;for _ in 0..c{acc*=p;for i in 0..k{d.push(d[i]*acc);}}}d.sort_unstable();d}#[doc=" Extends the prime list up to `max_n`."]pub fn reserve(&mut self,max_n:u32){if max_n<=self.max_n||max_n<2{return;}let limit=max_n.saturating_add(1);self.bit_len=to_ordinal(limit)as usize;if limit<=SQRT_THRESHOLD{self.bits=SQRT_BITS[..self.bit_len.div_ceil(64)].to_vec();}else{self.bits=vec![!0;self.bit_len.div_ceil(64)];let(wheels,medium_primes_begin)=make_wheels();const DENSE_BLOCK:u32=1<<25;for start in(0..limit).step_by(DENSE_BLOCK as usize){let right=start.saturating_add(DENSE_BLOCK).min(limit);for wheel in&wheels{let left=start/wheel.product*wheel.product;sieve_dense(&mut self.bits,to_ordinal(left),to_ordinal(right),wheel);}}let steps=ordinal_steps();let mut positions:Vec<_>=SQRT_PRIMES.iter().map(|&p|to_ordinal(p*p)).collect();let mut states:Vec<_>=SQRT_PRIMES.iter().map(|&p|STATES[(p%PERIOD)as usize]).collect();const SPARSE_BLOCK:u32=1<<22;for start in(0..limit).step_by(SPARSE_BLOCK as usize){let right=to_ordinal(start.saturating_add(SPARSE_BLOCK).min(limit));for i in medium_primes_begin..SQRT_PRIME_COUNT{(positions[i],states[i])=sieve_sparse(&mut self.bits,positions[i],right,i,states[i],&steps);}}for(value,&sqrt_bits)in self.bits.iter_mut().zip(&SQRT_BITS){*value=sqrt_bits;}}self.prime_count=WHEEL_PRIMES.partition_point(|&p|p<=max_n);if let Some((&last,rest))=self.bits.split_last(){self.prime_count+=rest.iter().map(|word|word.count_ones()as usize).sum::<usize>();let last_mask=if self.bit_len.is_multiple_of(64){!0}else{(1<<(self.bit_len%64))-1};self.prime_count+=(last&last_mask).count_ones()as usize;}self.max_n=max_n;}}#[derive(Clone,Debug)]pub struct PrimeListIter<'a>{wheel_indices:Range<u8>,middle_words:&'a[u64],front_word_base:u32,front_word_phase:u8,front_word:u64,back_word_base:u32,back_word_phase:u8,back_word:u64}impl PrimeListIter<'_>{#[inline(always)]fn load_front_word(&mut self)->bool{if let Some((&word,words))=self.middle_words.split_first(){self.middle_words=words;if self.front_word_phase==32{self.front_word_base+=PERIOD*2;self.front_word_phase=0;}else{self.front_word_base+=PERIOD;self.front_word_phase+=16;}self.front_word=word;true}else if self.back_word!=0{self.front_word_base=self.back_word_base;self.front_word_phase=self.back_word_phase;self.front_word=replace(&mut self.back_word,0);true}else{false}}#[inline(always)]fn load_back_word(&mut self)->bool{if let Some((&word,words))=self.middle_words.split_last(){self.middle_words=words;if self.back_word_phase==0{self.back_word_base-=PERIOD*2;self.back_word_phase=32;}else{self.back_word_base-=PERIOD;self.back_word_phase-=16;}self.back_word=word;true}else if self.front_word!=0{self.back_word_base=self.front_word_base;self.back_word_phase=self.front_word_phase;self.back_word=replace(&mut self.front_word,0);true}else{false}}}impl Iterator for PrimeListIter<'_>{type Item=u32;fn next(&mut self)->Option<Self::Item>{if let Some(index)=self.wheel_indices.next(){return Some(WHEEL_PRIMES[index as usize]);}loop{if self.front_word!=0{let bit=self.front_word.trailing_zeros();self.front_word&=self.front_word-1;return Some(self.front_word_base+ORDINAL_TO_VALUE[(self.front_word_phase+bit as u8)as usize]as u32);}if!self.load_front_word(){return None;}}}fn nth(&mut self,mut n:usize)->Option<Self::Item>{if n==0{return self.next();}for index in self.wheel_indices.by_ref(){if n==0{return Some(WHEEL_PRIMES[index as usize]);}n-=1;}loop{let count=self.front_word.count_ones()as usize;if n<count{for _ in 0..n{self.front_word&=self.front_word-1;}return self.next();}n-=count;self.front_word=0;if!self.load_front_word(){return None;}}}}impl DoubleEndedIterator for PrimeListIter<'_>{#[inline]fn next_back(&mut self)->Option<Self::Item>{loop{if self.back_word!=0{let bit=63-self.back_word.leading_zeros();self.back_word-=1<<bit;return Some(self.back_word_base+ORDINAL_TO_VALUE[(self.back_word_phase+bit as u8)as usize]as u32);}if!self.load_back_word(){return self.wheel_indices.next_back().map(|index|WHEEL_PRIMES[index as usize]);}}}fn nth_back(&mut self,mut n:usize)->Option<Self::Item>{if n==0{return self.next_back();}loop{let count=self.back_word.count_ones()as usize;if n<count{for _ in 0..n{let bit=63-self.back_word.leading_zeros();self.back_word-=1<<bit;}return self.next_back();}n-=count;self.back_word=0;if!self.load_back_word(){for index in self.wheel_indices.by_ref().rev(){if n==0{return Some(WHEEL_PRIMES[index as usize]);}n-=1;}return None;}}}}#[derive(Debug,Clone)]pub struct PrimeListTrialDivision<'p>{primes:PrimeListIter<'p>,n:u64}impl Iterator for PrimeListTrialDivision<'_>{type Item=(u64,u32);fn next(&mut self)->Option<Self::Item>{if self.n<=1{return None;}for p in self.primes.by_ref(){let p=u64::from(p);if p*p>self.n{break;}if self.n.is_multiple_of(p){let mut cnt=1u32;self.n/=p;while self.n.is_multiple_of(p){cnt+=1;self.n/=p;}return Some((p,cnt));}}if self.n>1{return Some((replace(&mut self.n,1),1));}None}}pub fn with_prime_list<F>(max_n:u32,f:F)where F:FnOnce(&PrimeList){thread_local!(static PRIME_LIST:UnsafeCell<PrimeList> =Default::default());PRIME_LIST.with(|cell|{unsafe{let pl=&mut*cell.get();pl.reserve(max_n);f(pl);};});}}
// codesnip-guard: _zeta_transform
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}
// codesnip-guard: ring
#[cfg_attr(any(),rustfmt::skip)]pub use self::ring::*;#[cfg_attr(any(),rustfmt::skip)]mod ring{use super::*;use std::{marker::PhantomData,num::Wrapping,ops::{Add,Mul}};pub trait SemiRing{type T:Clone;type Additive:AbelianMonoid<T=Self::T>;type Multiplicative:Monoid<T=Self::T>;#[doc=" additive identity: $0$"]fn zero()->Self::T{<Self::Additive as Unital>::unit()}fn is_zero(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::zero()}#[doc=" multiplicative identity: $1$"]fn one()->Self::T{<Self::Multiplicative as Unital>::unit()}fn is_one(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::one()}#[doc=" additive operaion: $+$"]fn add(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Magma>::operate(x,y)}#[doc=" multiplicative operaion: $+$"]fn mul(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Magma>::operate(x,y)}fn try_matrix_product(_a:&[Vec<Self::T>],_b:&[Vec<Self::T>])->Option<Vec<Vec<Self::T>>>{None}fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|mut sum,(x,y)|{Self::add_assign(&mut sum,&Self::mul(x,y));sum})}fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){Self::add_assign(x,&Self::mul(a,y));}}fn add_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Magma>::operate_assign(x,y);}fn mul_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Magma>::operate_assign(x,y);}}pub trait Ring:SemiRing<Additive:Invertible>{#[doc=" additive inverse: $-$"]fn neg(x:&Self::T)->Self::T{<Self::Additive as Invertible>::inverse(x)}#[doc=" additive right inversed operaion: $-$"]fn sub(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Invertible>::rinv_operate(x,y)}fn sub_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Invertible>::rinv_operate_assign(x,y);}}impl<R>Ring for R where R:SemiRing<Additive:Invertible>{}pub trait Field:Ring<Multiplicative:Invertible>{#[doc=" multiplicative inverse: $-$"]fn inv(x:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::inverse(x)}#[doc=" multiplicative right inversed operaion: $-$"]fn div(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::rinv_operate(x,y)}fn div_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Invertible>::rinv_operate_assign(x,y);}}impl<F>Field for F where F:Ring<Multiplicative:Invertible>{}pub trait DotProduct:Sized+Clone+Zero+Add<Output=Self>+Mul<Output=Self>{fn try_matrix_product(_a:&[Vec<Self>],_b:&[Vec<Self>])->Option<Vec<Vec<Self>>>{None}fn add_scaled_assign(x:&mut[Self],y:&[Self],a:&Self){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){*x=x.clone()+a.clone()*y.clone();}}fn dot_product(x:&[Self],y:&[Self])->Self{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|sum,(x,y)|sum+x.clone()*y.clone())}}macro_rules!impl_dot_product{($($t:ty)*)=>{$(impl DotProduct for$t{})*};}impl_dot_product!(u8 u16 u32 u64 usize u128 i8 i16 i32 i64 isize i128 f32 f64);impl<T>DotProduct for Wrapping<T>where Wrapping<T>:Clone+Zero+Add<Output=Wrapping<T>>+Mul<Output=Wrapping<T>>{}#[doc=" $+,\\times$"]pub struct AddMulOperation<T>where T:DotProduct+One{_marker:PhantomData<fn()->T>}impl<T>SemiRing for AddMulOperation<T>where T:DotProduct+One{type T=T;type Additive=AdditiveOperation<T>;type Multiplicative=MultiplicativeOperation<T>;#[inline]fn try_matrix_product(a:&[Vec<T>],b:&[Vec<T>])->Option<Vec<Vec<T>>>{T::try_matrix_product(a,b)}#[inline]fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{T::dot_product(x,y)}#[inline]fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){T::add_scaled_assign(x,y,a);}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}