#963219 (Rust) No.1092 modular arithmetic

提出ソース
結果

問題	No.1092 modular arithmetic
ユーザー	CoCo_Japan_pan
提出日時	2024-03-21 12:08:55
言語	Rust (1.77.0)
結果	AC
実行時間	24 ms / 2,000 ms
コード長	27,495 bytes
コンパイル時間	3,287 ms
コンパイル使用メモリ	193,468 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-03-21 12:09:05
合計ジャッジ時間	6,478 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	8 ms 6,676 KB
testcase_02	AC	1 ms 6,676 KB
testcase_03	AC	13 ms 6,676 KB
testcase_04	AC	11 ms 6,676 KB
testcase_05	AC	11 ms 6,676 KB
testcase_06	AC	8 ms 6,676 KB
testcase_07	AC	10 ms 6,676 KB
testcase_08	AC	12 ms 6,676 KB
testcase_09	AC	11 ms 6,676 KB
testcase_10	AC	9 ms 6,676 KB
testcase_11	AC	10 ms 6,676 KB
testcase_12	AC	8 ms 6,676 KB
testcase_13	AC	4 ms 6,676 KB
testcase_14	AC	22 ms 6,676 KB
testcase_15	AC	1 ms 6,676 KB
testcase_16	AC	3 ms 6,676 KB
testcase_17	AC	4 ms 6,676 KB
testcase_18	AC	13 ms 6,676 KB
testcase_19	AC	8 ms 6,676 KB
testcase_20	AC	13 ms 6,676 KB
testcase_21	AC	11 ms 6,676 KB
testcase_22	AC	13 ms 6,676 KB
testcase_23	AC	20 ms 6,676 KB
testcase_24	AC	7 ms 6,676 KB
testcase_25	AC	16 ms 6,676 KB
testcase_26	AC	20 ms 6,676 KB
testcase_27	AC	4 ms 6,676 KB
testcase_28	AC	16 ms 6,676 KB
testcase_29	AC	24 ms 6,676 KB
testcase_30	AC	16 ms 6,676 KB
testcase_31	AC	3 ms 6,676 KB
testcase_32	AC	14 ms 6,676 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// verification-helper: PROBLEM https://yukicoder.me/problems/no/1092

pub use __cargo_equip::prelude::*;

use dynamic_modint::{define_modint, DynamicModInt};
#[allow(unused_imports)]
use proconio::fastout;
use proconio::{/*fastout,*/ input, marker::Chars};

/*#[fastout]
fn main() {
    input! {
        p: u32,
        n: u32,
        a: [u32; n],
        s: Chars,
    }
    define_modint!(MOD, p);
    let a = a.into_iter().map(DynamicModInt::<MOD>::raw).collect::<Vec<_>>();
    let ans = a
        .iter()
        .skip(1)
        .zip(s.iter())
        .fold(a[0], |acc, (x, &c)| match c {
            '+' => acc + *x,
            '-' => acc - *x,
            '*' => acc * *x,
            '/' => acc / *x,
            _ => unreachable!(),
        });
    println!("{}", ans);
}*/
fn main() {
    let __proconio_stdout = ::std::io::stdout();
    let mut __proconio_stdout = ::std::io::BufWriter::new(__proconio_stdout.lock());
    #[allow(unused_macros)]
    macro_rules ! print { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: write ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    #[allow(unused_macros)]
    macro_rules ! println { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: writeln ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    let __proconio_res = {
        input! { p : u32 , n : u32 , a : [u32 ; n] , s : Chars , }
        define_modint!(MOD, p);
        let a = a
            .into_iter()
            .map(DynamicModInt::<MOD>::raw)
            .collect::<Vec<_>>();
        let ans = a
            .iter()
            .skip(1)
            .zip(s.iter())
            .fold(a[0], |acc, (x, &c)| match c {
                '+' => acc + *x,
                '-' => acc - *x,
                '*' => acc * *x,
                '/' => acc / *x,
                _ => unreachable!(),
            });
        println!("{}", ans);
    };
    <::std::io::BufWriter<::std::io::StdoutLock> as ::std::io::Write>::flush(
        &mut __proconio_stdout,
    )
    .unwrap();
    return __proconio_res;
}

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

///  # Bundled libraries
/// 
///  - `dynamic_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::dynamic_modint`
///  - `modint_traits 0.1.0 (path+████████████████████████████████████████████████████████████████████)` published in **missing**                                           licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
///  - `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`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
/// 
///  # 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 dynamic_modint {use crate::__cargo_equip::preludes::dynamic_modint::*;pub use crate::__cargo_equip::macros::dynamic_modint::*;use modint_traits::{ModInt,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::num::ParseIntError;use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;use std::sync::OnceLock;use std::marker::PhantomData;use std::fmt::Debug;pub trait ModContainer:'static+Debug+Clone+Copy+PartialEq+Eq{fn get_static_modulus()->&'static OnceLock<u32>;fn modulus()->u32{*Self::get_static_modulus().get().expect("haven't set modulus")}fn set_modulus(modulus:u32){Self::get_static_modulus().set(modulus).expect("already set modulus")}}#[macro_export]macro_rules!__cargo_equip_macro_def_dynamic_modint_define_modint{($name:ident,$modulus:expr)=>{#[derive(Debug,Clone,Copy,PartialEq,Eq)]pub enum$name{}impl$crate::__cargo_equip::crates::dynamic_modint::ModContainer for$name{fn get_static_modulus()->&'static std::sync::OnceLock<u32>{static ONCE:std::sync::OnceLock<u32> =std::sync::OnceLock::new();&ONCE}}DynamicModInt::<$name>::set_modulus($modulus);};}macro_rules!define_modint{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_dynamic_modint_define_modint!{$($tt)*})}#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash)]pub struct DynamicModInt<MOD:ModContainer>{value:u32,phantom:PhantomData<MOD>,}impl<MOD:ModContainer>Display for DynamicModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<MOD:ModContainer>Sum for DynamicModInt<MOD>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<MOD:ModContainer>Product for DynamicModInt<MOD>{fn product<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::raw(1),Mul::mul)}}impl<MOD:ModContainer>FromStr for DynamicModInt<MOD>{type Err=ParseIntError;fn from_str(s:&str)->Result<Self,ParseIntError>{i64::from_str(s).map(Self::new)}}impl<MOD:ModContainer>DynamicModInt<MOD>{pub fn set_modulus(modulus:u32){MOD::set_modulus(modulus);}pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}pub fn raw(x:u32)->Self{Self{value:x,phantom:PhantomData}}pub fn value(&self)->u32{self.value}pub fn modulus()->u32{MOD::modulus()}pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}pub fn inv(&self)->Self{ModInt::inv(self)}}impl<MOD:ModContainer>ModInt for DynamicModInt<MOD>{fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD::modulus()),phantom:PhantomData,}}fn raw(x:u32)->Self{Self{value:x,phantom:PhantomData}}fn value(&self)->u32{self.value}fn modulus()->u32{MOD::modulus()}}impl<MOD:ModContainer>Neg for DynamicModInt<MOD>{type Output=Self;fn neg(self)->Self{if self.value==0{Self{value:0,phantom:PhantomData}}else{Self{value:DynamicModInt::<MOD>::modulus()-self.value,phantom:PhantomData,}}}}impl<MOD:ModContainer>Add for DynamicModInt<MOD>{type Output=Self;fn add(mut self,rhs:Self)->Self{self+=rhs;self}}impl<MOD:ModContainer>AddAssign for DynamicModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=DynamicModInt::<MOD>::modulus(){self.value-=DynamicModInt::<MOD>::modulus();}}}impl<MOD:ModContainer>Sub for DynamicModInt<MOD>{type Output=Self;fn sub(mut self,rhs:Self)->Self{self-=rhs;self}}impl<MOD:ModContainer>SubAssign for DynamicModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=DynamicModInt::<MOD>::modulus();}self.value-=rhs.value;}}impl<MOD:ModContainer>Mul for DynamicModInt<MOD>{type Output=Self;fn mul(mut self,rhs:Self)->Self{self*=rhs;self}}impl<MOD:ModContainer>MulAssign for DynamicModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64%DynamicModInt::<MOD>::modulus()as u64)as u32;}}impl<MOD:ModContainer>Div for DynamicModInt<MOD>{type Output=Self;fn div(mut self,rhs:Self)->Self{self/=rhs;self}}#[allow(clippy::suspicious_op_assign_impl)]impl<MOD:ModContainer>DivAssign for DynamicModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}macro_rules!impl_binop_to_primitive{($($t:ty),*)=>{$(impl<MOD:ModContainer>Add<$t>for DynamicModInt<MOD>{type Output=Self;fn add(self,rhs:$t)->Self{self+DynamicModInt::new(rhs)}}impl<MOD:ModContainer>AddAssign<$t>for DynamicModInt<MOD>{fn add_assign(&mut self,rhs:$t){*self+=DynamicModInt::new(rhs);}}impl<MOD:ModContainer>Sub<$t>for DynamicModInt<MOD>{type Output=Self;fn sub(self,rhs:$t)->Self{self-DynamicModInt::new(rhs)}}impl<MOD:ModContainer>SubAssign<$t>for DynamicModInt<MOD>{fn sub_assign(&mut self,rhs:$t){*self-=DynamicModInt::new(rhs);}}impl<MOD:ModContainer>Mul<$t>for DynamicModInt<MOD>{type Output=Self;fn mul(self,rhs:$t)->Self{self*DynamicModInt::new(rhs)}}impl<MOD:ModContainer>MulAssign<$t>for DynamicModInt<MOD>{fn mul_assign(&mut self,rhs:$t){*self*=DynamicModInt::new(rhs);}}impl<MOD:ModContainer>Div<$t>for DynamicModInt<MOD>{type Output=Self;fn div(self,rhs:$t)->Self{self/DynamicModInt::new(rhs)}}impl<MOD:ModContainer>DivAssign<$t>for DynamicModInt<MOD>{fn div_assign(&mut self,rhs:$t){*self/=DynamicModInt::new(rhs);}})*}}impl_binop_to_primitive!(i8,i16,i32,i64,isize,i128,u8,u16,u32,u64,usize,u128);}
        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+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::raw(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);}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;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 crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;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 crate::__cargo_equip::preludes::proconio::*;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 crate::__cargo_equip::preludes::proconio::*;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{use crate::__cargo_equip::preludes::proconio::*;#[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()}}
        pub mod __proconio_derive_0_2_1 {pub use crate::__cargo_equip::macros::__proconio_derive_0_2_1::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
    }

    pub(crate) mod macros {
        pub mod dynamic_modint {pub use crate::__cargo_equip_macro_def_dynamic_modint_define_modint as define_modint;}
        pub mod __modint_traits_0_1_0 {}
        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 mod __proconio_derive_0_2_1 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_2_1_fastout as fastout};}
    }

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

    mod preludes {
        pub mod dynamic_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__modint_traits_0_1_0 as modint_traits;}
        pub mod __modint_traits_0_1_0 {}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__proconio_derive_0_2_1 as proconio_derive;}
        pub mod __proconio_derive_0_2_1 {}
    }
}