#993510 (Rust) No.803 Very Limited Xor Subset

• 問題: No.803 Very Limited Xor Subset
• ユーザー: CoCo_Japan_pan
• 提出日時: 2024-07-10 16:00:30
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 18,973 bytes
• コンパイル時間: 30,074 ms
• コンパイル使用メモリ: 402,572 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-10 16:01:03
• 合計ジャッジ時間: 32,441 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 43

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
pub use __cargo_equip::prelude::*;
use bit_matrix::BitMatrix;
use proconio::{fastout, input, marker::Usize1};
use static_modint::ModInt1000000007 as MInt;
#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        x: u32,
        a: [u32; n],
        t_l_r: [(u8, Usize1, Usize1); m],
    }
    let (mat, b) = {
        let mut mat = BitMatrix::new(32 + m, n);
        for (i, a) in a.into_iter().enumerate() {
            for bit in 0..32 {
                if ((a >> bit) & 1) > 0 {
                    mat.set(bit, i, true);
                }
            }
        }
        let mut b = vec![false; 32 + m];
        for bit in 0..32 {
            if ((x >> bit) & 1) > 0 {
                b[bit] = true;
            }
        }
        for (i, (t, l, r)) in t_l_r.into_iter().enumerate() {
            let i = i + 32;
            b[i] = t == 1;
            for j in l..=r {
                mat.set(i, j, true);
            }
        }
        (mat, b)
    };
    let ans = if let Some((free_dom, _)) = mat.linear_equation(&b) {
        MInt::new(2).pow(free_dom as u64)
    } else {
        MInt::new(0)
    };
    println!("{}", ans);
}
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
/// 
///  - `bit_matrix 0.1.0 (path+████████████████████████████████████████████████████████████)`                          published in ssh://git@github
    .com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::bit_matrix`
///  - `bitset 0.1.0 (path+███████████████████████████████████████████████████)`                                       published in ssh://git@github
    .com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitset_0_1_0`
///  - `internal_type_traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)` published in **missing**       
                                        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `modint_traits 0.1.0 (path+████████████████████████████████████████████████████████████████████)`               published in **missing**       
                                        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
///  - `static_modint 0.1.0 (path+█████████████████████████████████████████████████████████████████)`                  published in ssh://git@github
    .com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod bit_matrix {use crate::__cargo_equip::preludes::bit_matrix::*;use bitset::BitSet;use std::ops::{Add,AddAssign,Index,Mul,MulAssign}
            ;#[derive(Debug,Clone,PartialEq,Eq)]pub struct BitMatrix{height:usize,width:usize,data:Vec<BitSet>,}impl From<Vec<Vec<bool>>>for 
            BitMatrix{fn from(v:Vec<Vec<bool>>)->Self{let height=v.len();let width=v[0].len();let data=v.into_iter().map(BitSet::from).collect
            ();Self{height,width,data,}}}impl<const H:usize,const W:usize>From<[[bool;W];H]>for BitMatrix{fn from(v:[[bool;W];H])->Self{let height=H
            ;let width=W;let data=v.into_iter().map(BitSet::from).collect();Self{height,width,data,}}}impl From<Vec<BitSet>>for BitMatrix{fn from(v
            :Vec<BitSet>)->Self{let height=v.len();let width=v[0].size();Self{height,width,data:v,}}}impl<const H:usize>From<[BitSet;H]>for 
            BitMatrix{fn from(v:[BitSet;H])->Self{let height=H;let width=v[0].size();Self{height,width,data:v.to_vec(),}}}impl BitMatrix{pub fn new
            (height:usize,width:usize)->Self{Self{height,width,data:vec![BitSet::new(width);height],}}pub fn get(&self,row:usize,col:usize
            )->bool{assert!(row<self.height&&col<self.width);self.data[row][col]}pub fn set(&mut self,row:usize,col:usize,b:bool){assert!(row<self
            .height&&col<self.width);self.data[row].set(col,b);}pub fn gauss_jordan(&mut self,is_extended:bool)->usize{let mut rank=0;let col_end=if 
            is_extended{self.width-1}else{self.width};for col in 0..col_end{let mut pivot=None;for row in rank..self.height{if self
            .data[row][col]{pivot=Some(row);break;}}if let Some(pivot)=pivot{self.data.swap(rank,pivot);for row in 0..self.height{if row!=rank&&self
            .data[row][col]{unsafe{*self.data.as_mut_ptr().add(row)^=&self.data[rank];}}}rank+=1;}}rank}pub fn linear_equation(&self,b:&[bool]
            )->Option<(usize,Vec<bool>)>{assert_eq!(self.height,b.len());let mut mat=BitMatrix::new(self.height,self.width+1);#[allow(clippy
            ::needless_range_loop)]for i in 0..self.height{for j in 0..self.width{mat.set(i,j,self.get(i,j));}mat.set(i,self.width,b[i]);}let rank=mat
            .gauss_jordan(true);for i in rank..self.height{if mat.get(i,self.width){return None;}}let mut ans=vec![false;self.width];let mut cur_col=0
            ;for r in 0..rank{while cur_col<self.width&&!mat.get(r,cur_col){cur_col+=1;}assert!(cur_col<self.width);ans[cur_col]=mat.get(r,self.width
            );cur_col+=1;}let freedom=self.width-rank;Some((freedom,ans))}pub fn unit(n:usize)->Self{let mut res=Self::new(n,n);for i in 0..n{res.set
            (i,i,true);}res}pub fn transpose(&self)->Self{let mut res=Self::new(self.width,self.height);for i in 0..self.height{for j in 0..self
            .width{res.set(j,i,self.get(i,j));}}res}pub fn pow(&self,mut n:u64)->Self{assert_eq!(self.height,self.width);let mut res=Self::unit(self
            .height);let mut a=self.clone();while n>0{if(n&1)==1{res*=&a;}a=&a*&a;n>>=1;}res}}impl Index<usize>for BitMatrix{type Output=BitSet;fn 
            index(&self,index:usize)->&Self::Output{&self.data[index]}}impl AddAssign<&Self>for BitMatrix{fn add_assign(&mut self,rhs:&Self
            ){assert_eq!(self.height,rhs.height);assert_eq!(self.width,rhs.width);for(l,r)in self.data.iter_mut().zip(&rhs.data){*l^=r;}}}impl Add
            <&Self>for BitMatrix{type Output=Self;fn add(mut self,rhs:&Self)->Self{self+=rhs;self}}impl Mul<&BitMatrix>for&BitMatrix{type Output
            =BitMatrix;fn mul(self,rhs:&BitMatrix)->BitMatrix{assert_eq!(self.width,rhs.height);let mut ret=BitMatrix::new(self.height,rhs.width);let 
            rhs=rhs.transpose();for i in 0..self.height{for j in 0..rhs.height{ret.set(i,j,self.data[i].dot(&rhs.data[j]));}}ret}}impl Mul<&Self>for 
            BitMatrix{type Output=Self;fn mul(self,rhs:&Self)->Self{&self*rhs}}impl MulAssign<&Self>for BitMatrix{fn mul_assign(&mut self,rhs:&Self){
            *self=&*self*rhs;}}}
        pub mod __bitset_0_1_0 {use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Index,Not,Shl,ShlAssign,Shr,ShrAssign,}
            ;#[derive(Debug,Clone,PartialEq,Eq,Hash)]pub struct BitSet{buf:Vec<u64>,size:usize,}macro_rules!out_of_bounds{($size:expr,$i:expr
            )=>{assert!($i<$size,"index out of bounds: the len is {} but the index is {}",$size,$i);};}impl From<Vec<bool>>for BitSet{fn from(v:Vec
            <bool>)->Self{let size=v.len();let mut buf=vec![0;(size+63)/64];for i in 0..size{if v[i]{buf[i>>6]|=1<<(i&63);}}Self{buf,size}}}impl<const 
            N:usize>From<[bool;N]>for BitSet{fn from(v:[bool;N])->Self{let size=N;let mut buf=vec![0;(size+63)/64];for i in 0..size{if v[i]{buf[i>>6]|
            =1<<(i&63);}}Self{buf,size}}}impl BitSet{pub fn new(size:usize)->Self{let len=(size+63)/64;Self{buf:vec![0;len],size,}}#[inline]pub fn 
            size(&self)->usize{self.size}#[inline]pub fn get(&self,i:usize)->bool{out_of_bounds!(self.size,i);let x=self.buf[i>>6];let mask=1<<(i&63
            );(x&mask)!=0}#[inline]pub fn set(&mut self,i:usize,b:bool){out_of_bounds!(self.size,i);if b{self.buf[i>>6]|=1<<(i&63);}else{self.buf[i
            >>6]&=!(1<<(i&63));}}#[inline]pub fn flip(&mut self,i:usize){out_of_bounds!(self.size,i);self.buf[i>>6]^=1<<(i&63);}#[inline]pub fn 
            count_ones(&self)->u32{self.buf.iter().map(|&x|x.count_ones()).sum()}#[inline]pub fn count_zeros(&self)->u32{self.size as u32-self
            .count_ones()}#[inline]pub fn none(&self)->bool{self.count_ones()==0}#[inline]pub fn all(&self)->bool{self.count_ones()==self.size as 
            u32}#[inline]pub fn any(&self)->bool{self.count_ones()>0}#[inline]pub fn chomp(&mut self){let r=self.size&63;if r>0{if let Some(last)=self
            .buf.last_mut(){let d=64-r;*last=(*last<<d)>>d;}}}pub fn dot(&self,other:&Self)->bool{assert_eq!(self.size,other.size);self.buf.iter().zip
            (&other.buf).map(|(a,b)|((a&b).count_ones()&1)==1).fold(false,|acc,x|acc^x)}}impl Index<usize>for BitSet{type Output=bool;#[inline]fn 
            index(&self,i:usize)->&bool{out_of_bounds!(self.size,i);let x=self.buf[i>>6];let mask=1<<(i&63);if(x&mask)==0{&false}else{&true}}}impl<'a
            >BitXorAssign<&'a BitSet>for BitSet{#[inline]fn bitxor_assign(&mut self,rhs:&'a BitSet){for(a,b)in self.buf.iter_mut().zip(&rhs.buf){*a^
            =*b;}self.chomp();}}impl<'a>BitAndAssign<&'a BitSet>for BitSet{#[inline]fn bitand_assign(&mut self,rhs:&'a BitSet){for(a,b)in self.buf
            .iter_mut().zip(&rhs.buf){*a&=*b;}}}impl<'a>BitOrAssign<&'a BitSet>for BitSet{#[inline]fn bitor_assign(&mut self,rhs:&'a BitSet){for(a,b
            )in self.buf.iter_mut().zip(&rhs.buf){*a|=*b;}self.chomp();}}macro_rules!impl_bit_op{($op:ident,$op_assign:ident,$f:ident)=>{impl<'a>$op
            <&'a BitSet>for BitSet{type Output=BitSet;#[inline]fn$f(mut self,rhs:&'a BitSet)->Self::Output{self.$op_assign(rhs);self}}impl<'a,'b>$op
            <&'b BitSet>for&'a BitSet{type Output=BitSet;#[inline]fn$f(self,rhs:&'b BitSet)->Self::Output{let mut res=self.clone();res.$op_assign(rhs
            );res}}};}impl_bit_op!(BitXor,bitxor_assign,bitxor);impl_bit_op!(BitAnd,bitand_assign,bitand);impl_bit_op!(BitOr,bitor_assign,bitor);impl 
            Not for BitSet{type Output=Self;#[inline]fn not(mut self)->Self{for x in&mut self.buf{*x=!*x;}self.chomp();self}}impl<'a>Not for&'a 
            BitSet{type Output=BitSet;#[inline]fn not(self)->Self::Output{!self.clone()}}impl ShlAssign<usize>for BitSet{#[inline]fn shl_assign(&mut 
            self,rhs:usize){let q=rhs>>6;let r=rhs&63;if q>=self.buf.len(){for x in&mut self.buf{*x=0;}return;}if r==0{for i in(q..self.buf.len()).rev
            (){*unsafe{self.buf.get_unchecked_mut(i)}=*unsafe{self.buf.get_unchecked(i-q)};}}else{for i in(q+1..self.buf.len()).rev(){*unsafe{self.buf
            .get_unchecked_mut(i)}=(unsafe{self.buf.get_unchecked(i-q)}<<r)|(unsafe{self.buf.get_unchecked(i-q-1)}>>(64-r));}*unsafe{self.buf
            .get_unchecked_mut(q)}=unsafe{self.buf.get_unchecked(0)}<<r;}for x in&mut self.buf[..q]{*x=0;}self.chomp();}}impl ShrAssign<usize>for 
            BitSet{#[inline]fn shr_assign(&mut self,rhs:usize){let q=rhs>>6;let r=rhs&63;if q>=self.buf.len(){for x in&mut self.buf{*x=0;}return;}if r
            ==0{for i in 0..self.buf.len()-q{*unsafe{self.buf.get_unchecked_mut(i)}=*unsafe{self.buf.get_unchecked(i+q)};}}else{for i in 0..self.buf
            .len()-q-1{*unsafe{self.buf.get_unchecked_mut(i)}=(unsafe{self.buf.get_unchecked(i+q)}>>r)|(unsafe{self.buf.get_unchecked(i+q+1)}<<(64-r
            ));}let len=self.buf.len();*unsafe{self.buf.get_unchecked_mut(len-q-1)}=unsafe{self.buf.get_unchecked(len-1)}>>r;}let len=self.buf.len
            ();for x in&mut self.buf[len-q..]{*x=0;}}}macro_rules!impl_shift_op{($op:ident,$op_assign:ident,$f:ident)=>{impl$op<usize>for BitSet{type 
            Output=BitSet;#[inline]fn$f(mut self,rhs:usize)->Self::Output{self.$op_assign(rhs);self}}impl<'a>$op<usize>for&'a BitSet{type Output
            =BitSet;#[inline]fn$f(self,rhs:usize)->Self::Output{let mut res=self.clone();res.$op_assign(rhs);res}}};}impl_shift_op!(Shl,shl_assign,shl
            );impl_shift_op!(Shr,shr_assign,shr);}
        pub mod __internal_type_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add
            <Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove+Display+Debug{}pub trait Zero{fn zero()->Self
            ;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self
            ;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl 
            BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl 
            Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod __modint_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use 
            std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div
            <Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn 
            value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret
            *=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value(),Self::modulus());assert_eq!(g,1);Self::raw(x)}}fn 
            inv_gcd(a:u32,b:u32)->(u32,u32){assert!(a<b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0_i32;let mut m1=1_i32;while t!=0{let 
            u=s/t;s-=t*u;m0-=m1*(u as i32);std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=(b/s)as i32;}(s,m0 as u32)}pub 
            trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self,modulus:u32
            )->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl 
            RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for u64{#[inline]fn rem_euclid_u32
            (self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{let 
            casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn rem_euclid_u32(self,modulus:u32
            )->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus
            -val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32
            )->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*}
            ;}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);macro_rules!impl_rem_for_borrow{($($t:ty),*)=>{$(impl RemEuclidU32 
            for&$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(*self).rem_euclid_u32(modulus)}})*};}impl_rem_for_borrow!(u8,u16,u32,u64,usize
            ,u128,i8,i16,i32,i64,isize,i128);}
        pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt
            ,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub
            ,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007
            >;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for 
            StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD
            :u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const 
            MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add
            ::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I
            )->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s
            :&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self
            )->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x
            :u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self
            )}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn raw
            (x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for 
            StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value
            ,}}}}macro_rules!impl_ops{($trait:ident,$method:ident,$assign_trait:ident,$assign_method:ident)=>{impl<const MOD:u32,T>$trait<T>for 
            StaticModInt<MOD>where Self:$assign_trait<T>,{type Output=Self;fn$method(mut self,rhs:T)->Self{StaticModInt::<MOD>::$assign_method(&mut 
            self,rhs);self}}impl<const MOD:u32,T:RemEuclidU32>$assign_trait<T>for StaticModInt<MOD>{fn$assign_method(&mut self,rhs:T){StaticModInt
            ::<MOD>::$assign_method(self,Self::new(rhs));}}};}impl_ops!(Add,add,AddAssign,add_assign);impl_ops!(Sub,sub,SubAssign,sub_assign
            );impl_ops!(Mul,mul,MulAssign,mul_assign);impl_ops!(Div,div,DivAssign,div_assign);impl<const MOD:u32>AddAssign for StaticModInt<MOD>{fn 
            add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl<const MOD:u32>SubAssign for StaticModInt
            <MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl<const MOD:u32>MulAssign for 
            StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32(MOD);}}#[allow(clippy
            ::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv
            ();}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x)}}
            )*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
    }
    pub(crate) mod macros {
        pub mod bit_matrix {}
        pub mod __bitset_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod static_modint {}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
    mod preludes {
        pub mod bit_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__bitset_0_1_0 as bitset;}
        pub mod __bitset_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits
            ,__modint_traits_0_1_0 as modint_traits};}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX