結果
| 問題 | No.2733 Just K-times TSP |
| ユーザー |
 tttttaaa
|
| 提出日時 | 2024-04-20 07:03:45 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 177 ms / 2,000 ms |
| コード長 | 26,048 bytes |
| コンパイル時間 | 2,479 ms |
| コンパイル使用メモリ | 191,052 KB |
| 実行使用メモリ | 30,880 KB |
| 最終ジャッジ日時 | 2024-04-20 07:03:49 |
| 合計ジャッジ時間 | 3,934 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,944 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 1 ms
6,940 KB |
| testcase_05 | AC | 1 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 1 ms
6,940 KB |
| testcase_08 | AC | 1 ms
6,940 KB |
| testcase_09 | AC | 1 ms
6,944 KB |
| testcase_10 | AC | 1 ms
6,940 KB |
| testcase_11 | AC | 1 ms
6,944 KB |
| testcase_12 | AC | 1 ms
6,944 KB |
| testcase_13 | AC | 1 ms
6,940 KB |
| testcase_14 | AC | 3 ms
6,940 KB |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 1 ms
6,940 KB |
| testcase_17 | AC | 13 ms
6,940 KB |
| testcase_18 | AC | 15 ms
6,940 KB |
| testcase_19 | AC | 17 ms
6,944 KB |
| testcase_20 | AC | 4 ms
6,940 KB |
| testcase_21 | AC | 12 ms
6,944 KB |
| testcase_22 | AC | 121 ms
30,880 KB |
| testcase_23 | AC | 13 ms
6,940 KB |
| testcase_24 | AC | 75 ms
16,148 KB |
| testcase_25 | AC | 73 ms
16,084 KB |
| testcase_26 | AC | 1 ms
6,940 KB |
| testcase_27 | AC | 1 ms
6,940 KB |
| testcase_28 | AC | 2 ms
6,944 KB |
| testcase_29 | AC | 7 ms
6,944 KB |
| testcase_30 | AC | 16 ms
6,940 KB |
| testcase_31 | AC | 40 ms
8,288 KB |
| testcase_32 | AC | 86 ms
16,196 KB |
| testcase_33 | AC | 177 ms
30,788 KB |
ソースコード
#![allow(unused_imports, non_snake_case)]
pub use __cargo_equip::prelude::*;
use acl_modint::ModInt998244353 as Mint;
use kyopro_io::get;
use kyopro_modint::mint;
use kyopro_utils::*;
use std::{
io::{StdoutLock, Write},
mem,
};
pub struct ModStateBuilder {
MX_SIZE: usize,
B: usize,
powb: Vec<usize>,
}
impl ModStateBuilder {
fn new(mx_size: usize, base: usize) -> Self {
assert!(base > 1);
let mut powb = vec![1];
for i in 0..mx_size - 1 {
powb.push(powb[i] * base);
}
Self { MX_SIZE: mx_size, B: base, powb }
}
/// state の i 番目要素の値を変更します
pub fn modify(&self, mut state: usize, i: usize, v: usize) -> usize {
let b = self.powb[i];
let current = (state / b) % self.B;
state -= b * current;
state += b * v;
state
}
pub fn encode(&self, vals: &[usize]) -> usize {
vals.iter().enumerate().fold(0usize, |s, (i, &v)| s + self.powb[i] * v)
}
pub fn decode(&self, state: usize) -> Vec<usize> {
(0..self.MX_SIZE).map(|i| (state / self.powb[i]) % self.B).collect::<Vec<_>>()
}
/// state から i 番目要素の値を取得します
pub fn get_val(&self, state: usize, i: usize) -> usize {
(state / self.powb[i]) % self.B
}
pub fn get_max_state_value(&self) -> usize {
self.powb.iter().fold(0usize, |s, &v| s + v * (self.B - 1))
}
}
// #[test]
// fn test_modify() {
// let bui = ModStateBuilder::new(5, 5);
// let s = bui.modify(0, 0, 2);
// assert_eq!(s, 2);
// assert_eq!(0, bui.modify(2, 0, 0));
// let s = bui.modify(0, 1, 2);
// assert_eq!(s, 5 * 2);
// assert_eq!(0, bui.modify(5 * 2, 1, 0));
// assert_eq!(2, bui.modify(2 + 5 * 2, 1, 0));
// assert_eq!(2 + 5 * 1 + 25 * 1, bui.modify(2 + 5 * 2 + 25 * 1, 1, 1));
// }
const MULTIPLE_TEST_CASE: bool = false;
fn _main(_W: &mut std::io::BufWriter<StdoutLock>) {
let (N, M, K) = get!(usize, usize, usize);
let mut g = vec![vec![]; N];
for _ in 0..M {
let (u, v) = get!(usize, usize);
g[u - 1].push(v - 1);
g[v - 1].push(u - 1);
}
let bui = ModStateBuilder::new(N, K + 1);
let MX = bui.get_max_state_value();
let mut dp = mat![mint!(0); MX+1;N];
for i in 0..N {
dp[bui.modify(0, i, 1)][i] = mint!(1);
}
for i in 1..MX {
for j in 0..N {
let jcnt = bui.get_val(i, j);
if jcnt == 0 {
continue;
}
let curr_times = dp[i][j];
for &k in &g[j] {
let kcnt = bui.get_val(i, k);
if kcnt >= K {
continue;
}
dp[bui.modify(i, k, kcnt + 1)][k] += curr_times;
}
}
}
db!(dp);
let ans: Mint = dp[bui.get_max_state_value()].iter().sum();
writeln!(_W, "{}", ans).unwrap();
}
// writeln!(_W, "{}", ans).unwrap();
// {{{
fn main() {
let t = if MULTIPLE_TEST_CASE { get!(usize) } else { 1 };
let stdout = std::io::stdout();
let mut writer = std::io::BufWriter::new(stdout.lock());
for _ in 0..t {
let _ = _main(&mut writer);
}
}
// }}}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `ac-library-rs-parted-internal-math 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0`
/// - `ac-library-rs-parted-modint 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_modint`
/// - `kyopro-io 0.1.0 (path+████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_io`
/// - `kyopro-modint 0.1.0 (path+████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_modint`
/// - `kyopro-utils 0.1.0 (path+███████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_utils`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod __ac_library_rs_parted_internal_math_0_1_0 {pub use self::internal_math::*;mod internal_math{#![allow(dead_code)]use std::mem::swap;pub fn safe_mod(mut x:i64,m:i64)->i64{x%=m;if x<0{x+=m;}x}pub struct Barrett{pub _m:u32,pub im:u64,}impl Barrett{pub fn new(m:u32)->Barrett{Barrett{_m:m,im:(-1i64 as u64/m as u64).wrapping_add(1),}}pub fn umod(&self)->u32{self._m}#[allow(clippy::many_single_char_names)]pub fn mul(&self,a:u32,b:u32)->u32{mul_mod(a,b,self._m,self.im)}}#[allow(clippy::many_single_char_names)]pub fn mul_mod(a:u32,b:u32,m:u32,im:u64)->u32{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}#[allow(clippy::many_single_char_names)]pub fn pow_mod(x:i64,mut n:i64,m:i32)->i64{if m==1{return 0;}let _m=m as u32;let mut r:u64=1;let mut y:u64=safe_mod(x,m as i64)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 i64}pub fn is_prime(n:i32)->bool{let n=n as i64;match n{_ if n<=1=>return false,2|7|61=>return true,_ if n%2==0=>return false,_=>{}}let mut d=n-1;while d%2==0{d/=2;}for&a in&[2,7,61]{let mut t=d;let mut y=pow_mod(a,t,n as i32);while t!=n-1&&y!=1&&y!=n-1{y=y*y%n;t<<=1;}if y!=n-1&&t%2==0{return false;}}true}#[allow(clippy::many_single_char_names)]pub fn inv_gcd(a:i64,b:i64)->(i64,i64){let a=safe_mod(a,b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;swap(&mut s,&mut t);swap(&mut m0,&mut m1);}if m0<0{m0+=b/s;}(s,m0)}pub fn primitive_root(m:i32)->i32{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;}for i in(3..std::i32::MAX).step_by(2){if i as i64*i as i64>x as i64{break;}if x%i==0{divs[cnt]=i;cnt+=1;while x%i==0{x/=i;}}}if x>1{divs[cnt]=x;cnt+=1;}let mut g=2;loop{if(0..cnt).all(|i|pow_mod(g,((m-1)/divs[i])as i64,m)!=1){break g as i32;}g+=1;}}}}
pub mod acl_modint {use crate::__cargo_equip::preludes::acl_modint::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0 as internal_math;pub use self::modint::*;mod modint{use crate::__cargo_equip::preludes::acl_modint::*;use super::internal_math;use std::{cell::RefCell,convert::{Infallible,TryInto as _},fmt,hash::{Hash,Hasher},iter::{Product,Sum},marker::PhantomData,ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},str::FromStr,sync::atomic::{self,AtomicU32,AtomicU64},thread::LocalKey,};pub type ModInt1000000007=StaticModInt<Mod1000000007>;pub type ModInt998244353=StaticModInt<Mod998244353>;pub type ModInt=DynamicModInt<DefaultId>;#[derive(Copy,Clone,Eq,PartialEq)]#[repr(transparent)]pub struct StaticModInt<M>{val:u32,phantom:PhantomData<fn()->M>,}impl<M:Modulus>StaticModInt<M>{#[inline(always)]pub fn modulus()->u32{M::VALUE}#[inline]pub fn new<T:RemEuclidU32>(val:T)->Self{Self::raw(val.rem_euclid_u32(M::VALUE))}#[inline]pub fn raw(val:u32)->Self{Self{val,phantom:PhantomData,}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn pow(self,n:u64)->Self{<Self as ModIntBase>::pow(self,n)}#[inline]pub fn inv(self)->Self{if M::HINT_VALUE_IS_PRIME{if self.val()==0{panic!("attempt to divide by zero");}debug_assert!(internal_math::is_prime(M::VALUE.try_into().unwrap()),"{} is not a prime number",M::VALUE,);self.pow((M::VALUE-2).into())}else{Self::inv_for_non_prime_modulus(self)}}}impl<M:Modulus>ModIntBase for StaticModInt<M>{#[inline(always)]fn modulus()->u32{Self::modulus()}#[inline]fn raw(val:u32)->Self{Self::raw(val)}#[inline]fn val(self)->u32{self.val()}#[inline]fn inv(self)->Self{self.inv()}}pub trait Modulus:'static+Copy+Eq{const VALUE:u32;const HINT_VALUE_IS_PRIME:bool;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum Mod1000000007{}impl Modulus for Mod1000000007{const VALUE:u32=1_000_000_007;const HINT_VALUE_IS_PRIME:bool=true;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>{thread_local!{static BUTTERFLY_CACHE:RefCell<Option<ButterflyCache<Mod1000000007>>>=RefCell::default();}&BUTTERFLY_CACHE}}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum Mod998244353{}impl Modulus for Mod998244353{const VALUE:u32=998_244_353;const HINT_VALUE_IS_PRIME:bool=true;fn butterfly_cache()->&'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>{thread_local!{static BUTTERFLY_CACHE:RefCell<Option<ButterflyCache<Mod998244353>>>=RefCell::default();}&BUTTERFLY_CACHE}}pub struct ButterflyCache<M>{pub sum_e:Vec<StaticModInt<M>>,pub sum_ie:Vec<StaticModInt<M>>,}#[derive(Copy,Clone,Eq,PartialEq)]#[repr(transparent)]pub struct DynamicModInt<I>{val:u32,phantom:PhantomData<fn()->I>,}impl<I:Id>DynamicModInt<I>{#[inline]pub fn modulus()->u32{I::companion_barrett().umod()}#[inline]pub fn set_modulus(modulus:u32){if modulus==0{panic!("the modulus must not be 0");}I::companion_barrett().update(modulus);}#[inline]pub fn new<T:RemEuclidU32>(val:T)->Self{<Self as ModIntBase>::new(val)}#[inline]pub fn raw(val:u32)->Self{Self{val,phantom:PhantomData,}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn pow(self,n:u64)->Self{<Self as ModIntBase>::pow(self,n)}#[inline]pub fn inv(self)->Self{Self::inv_for_non_prime_modulus(self)}}impl<I:Id>ModIntBase for DynamicModInt<I>{#[inline]fn modulus()->u32{Self::modulus()}#[inline]fn raw(val:u32)->Self{Self::raw(val)}#[inline]fn val(self)->u32{self.val()}#[inline]fn inv(self)->Self{self.inv()}}pub trait Id:'static+Copy+Eq{fn companion_barrett()->&'static Barrett;}#[derive(Copy,Clone,Ord,PartialOrd,Eq,PartialEq,Hash,Debug)]pub enum DefaultId{}impl Id for DefaultId{fn companion_barrett()->&'static Barrett{static BARRETT:Barrett=Barrett::default();&BARRETT}}pub struct Barrett{m:AtomicU32,im:AtomicU64,}impl Barrett{#[inline]pub const fn new(m:u32)->Self{Self{m:AtomicU32::new(m),im:AtomicU64::new((-1i64 as u64/m as u64).wrapping_add(1)),}}#[inline]const fn default()->Self{Self::new(998_244_353)}#[inline]fn update(&self,m:u32){let im=(-1i64 as u64/m as u64).wrapping_add(1);self.m.store(m,atomic::Ordering::SeqCst);self.im.store(im,atomic::Ordering::SeqCst);}#[inline]fn umod(&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);internal_math::mul_mod(a,b,m,im)}}impl Default for Barrett{#[inline]fn default()->Self{Self::default()}}pub trait ModIntBase: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;#[inline]fn new<T:RemEuclidU32>(val:T)->Self{Self::raw(val.rem_euclid_u32(Self::modulus()))}#[inline]fn pow(self,mut n:u64)->Self{let mut x=self;let mut r=Self::raw(1);while n>0{if n&1==1{r*=x;}x*=x;n>>=1;}r}}pub trait RemEuclidU32{fn rem_euclid_u32(self,modulus:u32)->u32;}macro_rules!impl_rem_euclid_u32_for_small_signed{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self as i64).rem_euclid(i64::from(modulus))as _}})*}}impl_rem_euclid_u32_for_small_signed!(i8,i16,i32,i64,isize);impl RemEuclidU32 for i128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self.rem_euclid(i128::from(modulus))as _}}macro_rules!impl_rem_euclid_u32_for_small_unsigned{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}})*}}macro_rules!impl_rem_euclid_u32_for_large_unsigned{($($ty:tt),*)=>{$(impl RemEuclidU32 for$ty{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%(modulus as$ty))as _}})*}}impl_rem_euclid_u32_for_small_unsigned!(u8,u16,u32);impl_rem_euclid_u32_for_large_unsigned!(u64,u128);#[cfg(target_pointer_width="32")]impl_rem_euclid_u32_for_small_unsigned!(usize);#[cfg(target_pointer_width="64")]impl_rem_euclid_u32_for_large_unsigned!(usize);trait InternalImplementations:ModIntBase{#[inline]fn inv_for_non_prime_modulus(this:Self)->Self{let(gcd,x)=internal_math::inv_gcd(this.val().into(),Self::modulus().into());if gcd!=1{panic!("the multiplicative inverse does not exist");}Self::new(x)}#[inline]fn default_impl()->Self{Self::raw(0)}#[inline]fn from_str_impl(s:&str)->Result<Self,Infallible>{Ok(s.parse::<i64>().map(Self::new).unwrap_or_else(|_|todo!("parsing as an arbitrary precision integer?")))}#[inline]fn hash_impl(this:&Self,state:&mut impl Hasher){this.val().hash(state)}#[inline]fn display_impl(this:&Self,f:&mut fmt::Formatter)->fmt::Result{fmt::Display::fmt(&this.val(),f)}#[inline]fn debug_impl(this:&Self,f:&mut fmt::Formatter)->fmt::Result{fmt::Debug::fmt(&this.val(),f)}#[inline]fn neg_impl(this:Self)->Self{Self::sub_impl(Self::raw(0),this)}#[inline]fn add_impl(lhs:Self,rhs:Self)->Self{let modulus=Self::modulus();let mut val=lhs.val()+rhs.val();if val>=modulus{val-=modulus;}Self::raw(val)}#[inline]fn sub_impl(lhs:Self,rhs:Self)->Self{let modulus=Self::modulus();let mut val=lhs.val().wrapping_sub(rhs.val());if val>=modulus{val=val.wrapping_add(modulus)}Self::raw(val)}fn mul_impl(lhs:Self,rhs:Self)->Self;#[inline]fn div_impl(lhs:Self,rhs:Self)->Self{Self::mul_impl(lhs,rhs.inv())}}impl<M:Modulus>InternalImplementations for StaticModInt<M>{#[inline]fn mul_impl(lhs:Self,rhs:Self)->Self{Self::raw((u64::from(lhs.val())*u64::from(rhs.val())%u64::from(M::VALUE))as u32)}}impl<I:Id>InternalImplementations for DynamicModInt<I>{#[inline]fn mul_impl(lhs:Self,rhs:Self)->Self{Self::raw(I::companion_barrett().mul(lhs.val,rhs.val))}}macro_rules!impl_basic_traits{()=>{};(impl<$generic_param:ident:$generic_param_bound:tt>_ for$self:ty;$($rest:tt)*)=>{impl<$generic_param:$generic_param_bound>Default for$self{#[inline]fn default()->Self{Self::default_impl()}}impl<$generic_param:$generic_param_bound>FromStr for$self{type Err=Infallible;#[inline]fn from_str(s:&str)->Result<Self,Infallible>{Self::from_str_impl(s)}}impl<$generic_param:$generic_param_bound,V:RemEuclidU32>From<V>for$self{#[inline]fn from(from:V)->Self{Self::new(from)}}#[allow(clippy::derive_hash_xor_eq)]impl<$generic_param:$generic_param_bound>Hash for$self{#[inline]fn hash<H:Hasher>(&self,state:&mut H){Self::hash_impl(self,state)}}impl<$generic_param:$generic_param_bound>fmt::Display for$self{#[inline]fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{Self::display_impl(self,f)}}impl<$generic_param:$generic_param_bound>fmt::Debug for$self{#[inline]fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{Self::debug_impl(self,f)}}impl<$generic_param:$generic_param_bound>Neg for$self{type Output=$self;#[inline]fn neg(self)->$self{Self::neg_impl(self)}}impl<$generic_param:$generic_param_bound>Neg for&'_$self{type Output=$self;#[inline]fn neg(self)->$self{<$self>::neg_impl(*self)}}impl_basic_traits!($($rest)*);};}impl_basic_traits!{impl<M:Modulus>_ for StaticModInt<M>;impl<I:Id>_ for DynamicModInt<I>;}macro_rules!impl_bin_ops{()=>{};(for<$($generic_param:ident:$generic_param_bound:tt),*><$lhs_ty:ty>~<$rhs_ty:ty>->$output:ty{{$lhs_body:expr}~{$rhs_body:expr}}$($rest:tt)*)=>{impl<$($generic_param:$generic_param_bound),*>Add<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn add(self,rhs:$rhs_ty)->$output{<$output>::add_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Sub<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn sub(self,rhs:$rhs_ty)->$output{<$output>::sub_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Mul<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn mul(self,rhs:$rhs_ty)->$output{<$output>::mul_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl<$($generic_param:$generic_param_bound),*>Div<$rhs_ty>for$lhs_ty{type Output=$output;#[inline]fn div(self,rhs:$rhs_ty)->$output{<$output>::div_impl(apply($lhs_body,self),apply($rhs_body,rhs))}}impl_bin_ops!($($rest)*);};}macro_rules!impl_assign_ops{()=>{};(for<$($generic_param:ident:$generic_param_bound:tt),*><$lhs_ty:ty>~=<$rhs_ty:ty>{_~={$rhs_body:expr}}$($rest:tt)*)=>{impl<$($generic_param:$generic_param_bound),*>AddAssign<$rhs_ty>for$lhs_ty{#[inline]fn add_assign(&mut self,rhs:$rhs_ty){*self=*self+apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>SubAssign<$rhs_ty>for$lhs_ty{#[inline]fn sub_assign(&mut self,rhs:$rhs_ty){*self=*self-apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>MulAssign<$rhs_ty>for$lhs_ty{#[inline]fn mul_assign(&mut self,rhs:$rhs_ty){*self=*self*apply($rhs_body,rhs);}}impl<$($generic_param:$generic_param_bound),*>DivAssign<$rhs_ty>for$lhs_ty{#[inline]fn div_assign(&mut self,rhs:$rhs_ty){*self=*self/apply($rhs_body,rhs);}}impl_assign_ops!($($rest)*);};}#[inline]fn apply<F:FnOnce(X)->O,X,O>(f:F,x:X)->O{f(x)}impl_bin_ops!{for<M:Modulus><StaticModInt<M> >~<StaticModInt<M> >->StaticModInt<M>{{|x|x}~{|x|x}}for<M:Modulus><StaticModInt<M> >~<&'_ StaticModInt<M> >->StaticModInt<M>{{|x|x}~{|&x|x}}for<M:Modulus><&'_ StaticModInt<M> >~<StaticModInt<M> >->StaticModInt<M>{{|&x|x}~{|x|x}}for<M:Modulus><&'_ StaticModInt<M> >~<&'_ StaticModInt<M> >->StaticModInt<M>{{|&x|x}~{|&x|x}}for<I:Id><DynamicModInt<I> >~<DynamicModInt<I> >->DynamicModInt<I>{{|x|x}~{|x|x}}for<I:Id><DynamicModInt<I> >~<&'_ DynamicModInt<I>>->DynamicModInt<I>{{|x|x}~{|&x|x}}for<I:Id><&'_ DynamicModInt<I>>~<DynamicModInt<I> >->DynamicModInt<I>{{|&x|x}~{|x|x}}for<I:Id><&'_ DynamicModInt<I>>~<&'_ DynamicModInt<I>>->DynamicModInt<I>{{|&x|x}~{|&x|x}}for<M:Modulus,T:RemEuclidU32><StaticModInt<M> >~<T>->StaticModInt<M>{{|x|x}~{StaticModInt::<M>::new}}for<I:Id,T:RemEuclidU32><DynamicModInt<I> >~<T>->DynamicModInt<I>{{|x|x}~{DynamicModInt::<I>::new}}}impl_assign_ops!{for<M:Modulus><StaticModInt<M> >~=<StaticModInt<M> >{_~={|x|x}}for<M:Modulus><StaticModInt<M> >~=<&'_ StaticModInt<M> >{_~={|&x|x}}for<I:Id><DynamicModInt<I>>~=<DynamicModInt<I> >{_~={|x|x}}for<I:Id><DynamicModInt<I>>~=<&'_ DynamicModInt<I>>{_~={|&x|x}}for<M:Modulus,T:RemEuclidU32><StaticModInt<M> >~=<T>{_~={StaticModInt::<M>::new}}for<I:Id,T:RemEuclidU32><DynamicModInt<I>>~=<T>{_~={DynamicModInt::<I>::new}}}macro_rules!impl_folding{()=>{};(impl<$generic_param:ident:$generic_param_bound:tt>$trait:ident<_>for$self:ty{fn$method:ident(_)->_{_($unit:expr,$op:expr)}}$($rest:tt)*)=>{impl<$generic_param:$generic_param_bound>$trait<Self>for$self{#[inline]fn$method<S>(iter:S)->Self where S:Iterator<Item=Self>,{iter.fold($unit,$op)}}impl<'a,$generic_param:$generic_param_bound>$trait<&'a Self>for$self{#[inline]fn$method<S>(iter:S)->Self where S:Iterator<Item=&'a Self>,{iter.fold($unit,$op)}}impl_folding!($($rest)*);};}impl_folding!{impl<M:Modulus>Sum<_>for StaticModInt<M>{fn sum(_)->_{_(Self::raw(0),Add::add)}}impl<M:Modulus>Product<_>for StaticModInt<M>{fn product(_)->_{_(Self::raw(1),Mul::mul)}}impl<I:Id>Sum<_>for DynamicModInt<I>{fn sum(_)->_{_(Self::raw(0),Add::add)}}impl<I:Id>Product<_>for DynamicModInt<I>{fn product(_)->_{_(Self::raw(1),Mul::mul)}}}}}
pub mod kyopro_io {pub use crate::__cargo_equip::macros::kyopro_io::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_io_get{($t:ty)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*;$n:expr)=>{(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty;;)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t;;)).collect::<Vec<_>>()};}macro_rules!get{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_io_get!{$($tt)*})}}
pub mod kyopro_modint {pub use crate::__cargo_equip::macros::kyopro_modint::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_modint_mint{($num:expr)=>{Mint::new($num)};()=>{Mint::new(0)};}macro_rules!mint{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_modint_mint!{$($tt)*})}}
pub mod kyopro_utils {pub use crate::__cargo_equip::macros::kyopro_utils::*;use std::ops::{Add,Rem};#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_mat{($($e:expr),*)=>{Vec::from(vec![$($e),*])};($($e:expr,)*)=>{Vec::from(vec![$($e),*])};($e:expr;$d:expr)=>{Vec::from(vec![$e;$d])};($e:expr;$d:expr$(;$ds:expr)+)=>{Vec::from(vec![mat![$e$(;$ds)*];$d])};}macro_rules!mat{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_mat!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_ec{($($num:expr),*)=>{let mut tmp=vec![];$(tmp.push(format!("{}",$num));)*print!("{}
",tmp.join(" "));};}macro_rules!ec{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_ec!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_YesNo{($num:expr)=>{if($num)as i64==0{println!("No");}else{println!("Yes");}};}macro_rules!YesNo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_YesNo!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_Yes{()=>{println!("Yes");};}macro_rules!Yes{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_Yes!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_No{()=>{println!("No");};}macro_rules!No{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_No!{$($tt)*})}pub trait SetMinMax{fn setmin(&mut self,v:Self)->bool;fn setmax(&mut self,v:Self)->bool;}impl<T>SetMinMax for T where T:PartialOrd,{fn setmin(&mut self,v:T)->bool{*self>v&&{*self=v;true}}fn setmax(&mut self,v:T)->bool{*self<v&&{*self=v;true}}}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_chmax{($lhs:expr,$rhs:expr)=>{if$lhs<$rhs{let tmp=$rhs;$lhs=tmp;true}else{false}};}macro_rules!chmax{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_chmax!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_chmin{($lhs:expr,$rhs:expr)=>{if$lhs>$rhs{let tmp=$rhs;$lhs=tmp;true}else{false}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_chmin!{$($tt)*})}pub fn print_vec<T>(v:&[T])where T:std::fmt::Display,{for i in 0..v.len(){print!("{}{}",v[i],if i+1==v.len(){""}else{" "});}println!();}pub fn pmod<T:Copy+Add<Output=T>+Rem<Output=T>>(x:T,m:T)->T{((x%m)+m)%m}pub fn lower_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>=*x{return 0;}let mut l=0;let mut r=a.len();while l+1<r{let m=(l+r)/2;if a[m]<*x{l=m;}else{r=m;}}r}pub fn upper_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>*x{return 0;}let mut l=0;let mut r=a.len();while l+1<r{let m=(l+r)/2;if a[m]<=*x{l=m;}else{r=m;}}r}#[allow(unused_macros)]#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_db{($($a:expr),*$(,)*)=>{#[cfg(debug_assertions)]eprintln!(concat!($("| ",stringify!($a),"={:?} "),*),$(&$a),*);};}macro_rules!db{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_db!{$($tt)*})}#[allow(unused_macros)]#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_db2d{($vec:expr)=>{#[cfg(debug_assertions)]{eprintln!("> {}=",stringify!($vec));for a in$vec.iter(){eprintln!("> {:?}",a);}}};}macro_rules!db2d{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_db2d!{$($tt)*})}#[derive(PartialEq,PartialOrd)]pub struct OrdF<T>(pub T);impl<T:PartialEq>Eq for OrdF<T>{}impl<T:PartialOrd>Ord for OrdF<T>{fn cmp(&self,other:&OrdF<T>)->std::cmp::Ordering{self.0.partial_cmp(&other.0).unwrap()}}}
}
pub(crate) mod macros {
pub mod __ac_library_rs_parted_internal_math_0_1_0 {}
pub mod acl_modint {}
pub mod kyopro_io {pub use crate::__cargo_equip_macro_def_kyopro_io_get as get;}
pub mod kyopro_modint {pub use crate::__cargo_equip_macro_def_kyopro_modint_mint as mint;}
pub mod kyopro_utils {pub use crate::{__cargo_equip_macro_def_kyopro_utils_No as No,__cargo_equip_macro_def_kyopro_utils_Yes as Yes,__cargo_equip_macro_def_kyopro_utils_YesNo as YesNo,__cargo_equip_macro_def_kyopro_utils_chmax as chmax,__cargo_equip_macro_def_kyopro_utils_chmin as chmin,__cargo_equip_macro_def_kyopro_utils_db as db,__cargo_equip_macro_def_kyopro_utils_db2d as db2d,__cargo_equip_macro_def_kyopro_utils_ec as ec,__cargo_equip_macro_def_kyopro_utils_mat as mat};}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod __ac_library_rs_parted_internal_math_0_1_0 {}
pub mod acl_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_math_0_1_0 as __acl_internal_math;}
pub mod kyopro_io {}
pub mod kyopro_modint {}
pub mod kyopro_utils {}
}
}