結果

問題 No.2231 Surprising Flash!
ユーザー 37kt
提出日時 2023-07-12 15:16:21
言語 Rust
(1.83.0 + proconio)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 50,391 bytes
コンパイル時間 12,840 ms
コンパイル使用メモリ 403,404 KB
最終ジャッジ日時 2024-06-12 07:55:42
合計ジャッジ時間 13,797 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error[E0659]: `proconio` is ambiguous
 --> src/main.rs:7:5
  |
7 | use proconio::{
  |     ^^^^^^^^ ambiguous name
  |
  = note: ambiguous because of a conflict between a name from a glob import and an outer scope during import or macro resolution
  = note: `proconio` could refer to a crate passed with `--extern`
  = help: use `::proconio` to refer to this crate unambiguously
note: `proconio` could also refer to the module imported here
 --> src/main.rs:1:9
  |
1 | pub use __cargo_equip::prelude::*;
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^
  = help: consider adding an explicit import of `proconio` to disambiguate
  = help: or use `crate::proconio` to refer to this module unambiguously

warning: unused import: `crate::__cargo_equip::prelude::*`
   --> src/main.rs:136:13
    |
136 |     pub use crate::__cargo_equip::prelude::*;
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: unused import: `crate::__cargo_equip::prelude::*`
   --> src/main.rs:322:13
    |
322 |     pub use crate::__cargo_equip::prelude::*;
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0659`.
error: could not compile `main` (bin "main") due to 1 previous error; 2 warnings emitted

ソースコード

diff #
プレゼンテーションモードにする

pub use __cargo_equip::prelude::*;
use std::cmp::Ordering;
use convolution_ntt_friendly::convolution_ntt_friendly;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use modint::ModInt998244353 as Mint;
use crate::rolling_hash::RollingHashModInt61;
fn main() {
    input! {
        t: usize,
    }
    let mut rng = Pcg64Fast::default();
    for _ in 0..t {
        let mut cv = vec![Mint::new(0); 256];
        let mut vc = vec![Mint::new(0); 256];
        for c in b'a'..=b'z' {
            cv[c as usize] = rng.u32().into();
            vc[c as usize] = cv[c as usize].inv();
        }
        input! {
            n: usize,
            m: usize,
            mut s: Bytes,
            t: Bytes,
        }
        let mut sa = s.clone();
        let mut g = vec![0; n + 1];
        for i in 0..n {
            g[i + 1] = g[i];
            if s[i] != b'?' {
                g[i + 1] += 1;
            } else {
                sa[i] = b'a';
            }
        }
        let hs = RollingHashModInt61::new(&sa);
        let ht = RollingHashModInt61::new(&t);
        let a: Vec<_> = s.iter().map(|&x| cv[x as usize]).collect();
        let b: Vec<_> = t.iter().rev().map(|&x| vc[x as usize]).collect();
        let c = convolution_ntt_friendly(a, b);
        let mut p = !0;
        for i in 0..=n - m {
            let cnt = g[i + m] - g[i];
            if c[i + m - 1].val() == cnt {
                if p == !0 {
                    p = i;
                } else {
                    let mut f = Ordering::Equal;
                    if p + m <= i {
                        f = f.then(ht.compare(.., &hs, p..p + m));
                        f = f.then(hs.compare(i..i + m, &ht, ..));
                    } else {
                        let d = i - p;
                        f = f.then(ht.compare(..d, &hs, p..p + d));
                        f = f.then(ht.compare(d.., &ht, ..m - d));
                        f = f.then(hs.compare(p + m..p + m + d, &ht, m - d..));
                    }
                    if f.is_gt() {
                        p = i;
                    }
                }
            }
        }
        if p == !0 {
            println!("-1");
        } else {
            for i in 0..n {
                if s[i] == b'?' {
                    s[i] = b'a';
                }
            }
            for i in p..p + m {
                s[i] = t[i - p];
            }
            for i in 0..n {
                print!("{}", s[i] as char);
            }
            println!();
        }
    }
}
#[derive(Clone)]
pub struct Pcg64Fast(u128);
const R: f64 = 1.0 / 0xffff_ffff_ffff_ffff_u64 as f64;
impl Default for Pcg64Fast {
    fn default() -> Self {
        Self(
            std::time::SystemTime::now()
                .duration_since(std::time::UNIX_EPOCH)
                .unwrap()
                .as_nanos()
                | 1,
        )
    }
}
impl Pcg64Fast {
    #[inline]
    pub fn new(state: u128) -> Self {
        Self(state | 1)
    }
    #[inline]
    pub fn u32(&mut self) -> u32 {
        self.u64() as u32
    }
    #[inline(always)]
    pub fn u64(&mut self) -> u64 {
        self.0 = self
            .0
            .wrapping_mul(0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645);
        let rot = (self.0 >> 122) as u32;
        let xsl = (self.0 >> 64) as u64 ^ self.0 as u64;
        xsl.rotate_right(rot)
    }
    #[inline]
    pub fn f64(&mut self) -> f64 {
        self.u64() as f64 * R
    }
}
mod modint61 {
    pub use crate::__cargo_equip::prelude::*;
use std::{
        fmt::{Debug, Display},
        ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
    };
    const P: u64 = (1 << 61) - 1;
    #[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
    pub struct ModInt61(u64);
    impl ModInt61 {
        #[inline]
        pub fn new(x: impl Into<ModInt61>) -> Self {
            x.into()
        }
        #[inline]
        pub fn raw(val: u64) -> Self {
            Self(val)
        }
        #[inline]
        pub fn val(self) -> u64 {
            self.0
        }
        #[inline]
        pub fn modulus() -> u64 {
            P
        }
        pub fn pow(mut self, mut k: usize) -> Self {
            let mut res = Self::raw(1);
            while k != 0 {
                if k & 1 != 0 {
                    res *= self;
                }
                k >>= 1;
                self *= self;
            }
            res
        }
        pub fn inv(self) -> Self {
            self.pow(P as usize - 2)
        }
    }
    impl Display for ModInt61 {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }
    impl Debug for ModInt61 {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }
    impl Neg for ModInt61 {
        type Output = Self;
        fn neg(self) -> Self::Output {
            if self.0 == 0 {
                self
            } else {
                Self(P - self.0)
            }
        }
    }
    impl Neg for &ModInt61 {
        type Output = ModInt61;
        fn neg(self) -> Self::Output {
            -*self
        }
    }
    impl AddAssign for ModInt61 {
        fn add_assign(&mut self, rhs: Self) {
            self.0 += rhs.0;
            if self.0 >= P {
                self.0 -= P;
            }
        }
    }
    impl SubAssign for ModInt61 {
        fn sub_assign(&mut self, rhs: Self) {
            *self += -rhs;
        }
    }
    impl MulAssign for ModInt61 {
        fn mul_assign(&mut self, rhs: Self) {
            let t = self.0 as u128 * rhs.0 as u128;
            let t = (t >> 61) as u64 + (t as u64 & P);
            self.0 = if t >= P { t - P } else { t }
        }
    }
    impl DivAssign for ModInt61 {
        fn div_assign(&mut self, rhs: Self) {
            *self *= rhs.inv();
        }
    }
    macro_rules! impl_from_integer {
        ($(($t1:ty, $t2:ty)),*) => {
            $(
                impl From<$t1> for ModInt61 {
                    fn from(x: $t1) -> Self {
                        Self((x as $t2).rem_euclid(P as $t2) as u64)
                    }
                }
            )*
        };
    }
    impl_from_integer!(
        (i8, i64),
        (i16, i64),
        (i32, i64),
        (i64, i64),
        (isize, i64),
        (i128, i128),
        (u8, u64),
        (u16, u64),
        (u32, u64),
        (u64, u64),
        (usize, u64),
        (u128, u128)
    );
    macro_rules! impl_ops {
        ($(
            $trait:ident,
            $trait_assign:ident,
            $fn:ident,
            $fn_assign:ident,
        )*) => {$(
            impl $trait_assign<&ModInt61> for ModInt61 {
                fn $fn_assign(&mut self, rhs: &ModInt61) {
                    self.$fn_assign(*rhs);
                }
            }
            impl $trait<&ModInt61> for ModInt61 {
                type Output = ModInt61;
                fn $fn(mut self, rhs: &ModInt61) -> Self::Output {
                    self.$fn_assign(*rhs);
                    self
                }
            }
            impl $trait<ModInt61> for &ModInt61 {
                type Output = ModInt61;
                fn $fn(self, rhs: ModInt61) -> Self::Output {
                    (*self).$fn(rhs)
                }
            }
            impl $trait<ModInt61> for ModInt61 {
                type Output = ModInt61;
                fn $fn(mut self, rhs: ModInt61) -> Self::Output {
                    self.$fn_assign(rhs);
                    self
                }
            }
            impl $trait<&ModInt61> for &ModInt61 {
                type Output = ModInt61;
                fn $fn(self, rhs: &ModInt61) -> Self::Output {
                    (*self).$fn(&*rhs)
                }
            }
        )*};
    }
    impl_ops! {
        Add, AddAssign, add, add_assign,
        Sub, SubAssign, sub, sub_assign,
        Mul, MulAssign, mul, mul_assign,
        Div, DivAssign, div, div_assign,
    }
}
mod rolling_hash {
    pub use crate::__cargo_equip::prelude::*;
use super::modint61::ModInt61;
    use super::Pcg64Fast;
    use std::{
        cmp::Ordering,
        marker::PhantomData,
        ops::{Add, Bound, Mul, Neg, RangeBounds},
    };
    pub type RollingHashModInt61<'a, C> = RollingHash<'a, C, ModInt61>;
    pub struct GenBaseImpl<T>(PhantomData<fn() -> T>);
    pub trait GenBase {
        type H;
        fn base() -> Self::H;
    }
    impl GenBase for GenBaseImpl<ModInt61> {
        type H = ModInt61;
        fn base() -> ModInt61 {
            fn gen() -> ModInt61 {
                const FACTORS: [usize; 12] = [2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321];
                let mut rng = Pcg64Fast::default();
                loop {
                    let x = ModInt61::new(rng.u64());
                    if FACTORS
                        .iter()
                        .all(|&f| x.pow((ModInt61::modulus() as usize - 1) / f).val() > 1)
                    {
                        return x;
                    }
                }
            }
            thread_local! {
                static BASE: ModInt61 = gen();
            }
            BASE.with(|base| *base)
        }
    }
    #[derive(Clone)]
    pub struct RollingHash<'a, C, H>
    where
        C: Copy + Eq + Into<H>,
        H: Copy + Eq + Add<Output = H> + Mul<Output = H> + Neg<Output = H>,
        GenBaseImpl<H>: GenBase<H = H>,
    {
        s: &'a [C],
        hs: Box<[H]>,
        pw: Box<[H]>,
    }
    impl<'a, C, H> RollingHash<'a, C, H>
    where
        C: Copy + Eq + Into<H>,
        H: Copy + Eq + From<u64> + Add<Output = H> + Mul<Output = H> + Neg<Output = H>,
        GenBaseImpl<H>: GenBase<H = H>,
    {
        pub fn new(s: &'a [C]) -> Self {
            let n = s.len();
            let base = GenBaseImpl::<H>::base();
            let mut hs = vec![H::from(0); n + 1];
            let mut pw = vec![H::from(1); n + 1];
            for i in 0..n {
                hs[i + 1] = hs[i] * base + s[i].into();
                pw[i + 1] = pw[i] * base;
            }
            Self {
                s,
                hs: hs.into_boxed_slice(),
                pw: pw.into_boxed_slice(),
            }
        }
        pub fn len(&self) -> usize {
            self.s.len()
        }
        pub fn get(&self, index: impl RangeBounds<usize>) -> H {
            let (l, r) = range_to_pair(index, self.len());
            self.hs[l] * -self.pw[r - l] + self.hs[r]
        }
        pub fn lcp(
            &self,
            index1: impl RangeBounds<usize>,
            other: &Self,
            index2: impl RangeBounds<usize>,
        ) -> usize {
            let (l1, r1) = range_to_pair(index1, self.len());
            let (l2, r2) = range_to_pair(index2, other.len());
            let n = (r1 - l1).min(r2 - l2);
            let mut ok = 0;
            let mut ng = n + 1;
            while ok + 1 < ng {
                let md = (ok + ng) / 2;
                if self.get(l1..l1 + md) == other.get(l2..l2 + md) {
                    ok = md;
                } else {
                    ng = md;
                }
            }
            ok
        }
    }
    impl<'a, C, H> RollingHash<'a, C, H>
    where
        C: Copy + Eq + Into<H> + Ord,
        H: Copy + Eq + From<u64> + Add<Output = H> + Mul<Output = H> + Neg<Output = H>,
        GenBaseImpl<H>: GenBase<H = H>,
    {
        pub fn compare(
            &self,
            index1: impl RangeBounds<usize>,
            other: &Self,
            index2: impl RangeBounds<usize>,
        ) -> Ordering {
            let (l1, r1) = range_to_pair(index1, self.len());
            let (l2, r2) = range_to_pair(index2, other.len());
            let n = self.lcp(l1..r1, other, l2..r2);
            if l1 + n == r1 {
                if l2 + n == r2 {
                    Ordering::Equal
                } else {
                    Ordering::Less
                }
            } else if l2 + n == r2 {
                Ordering::Greater
            } else {
                self.s[l1 + n].cmp(&other.s[l2 + n])
            }
        }
    }
    fn range_to_pair(range: impl RangeBounds<usize>, n: usize) -> (usize, usize) {
        let l = match range.start_bound() {
            Bound::Included(&l) => l,
            Bound::Excluded(&l) => l + 1,
            Bound::Unbounded => 0,
        };
        let r = match range.end_bound() {
            Bound::Included(&r) => r + 1,
            Bound::Excluded(&r) => r,
            Bound::Unbounded => n,
        };
        (l, r)
    }
}
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
/// 
///  - `convolution-naive 0.1.0 (path+██████████████████████████████████████████████████████████████████)`               published in **missing** 
    licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::__convolution_naive_0_1_0`
///  - `convolution-ntt-friendly 0.1.0 (path+█████████████████████████████████████████████████████████████████████████)` published in **missing** 
    licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::convolution_ntt_friendly`
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`                                                                
    licensed under `MIT/Apache-2.0`    as `crate::__cargo_equip::crates::__lazy_static_1_4_0`
///  - `modint 0.1.0 (path+█████████████████████████████████████████████████████████)`                                   published in **missing** 
    licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::modint`
///  - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`                                                                   
    licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
/// 
///  # License and Copyright Notices
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      Copyright (c) 2010 The Rust Project Developers
/// 
///      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.
///      ```
/// 
///  - `proconio 0.4.3 (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 __convolution_naive_0_1_0 {use crate::__cargo_equip::preludes::__convolution_naive_0_1_0::*;use modint::ModInt;pub fn 
            convolution_naive<T:ModInt>(a:&[T],b:&[T])->Vec<T>{let n=a.len();let m=b.len();if n==0||m==0{return vec![];}let l=n+m-1;let mut c=vec![0
            .into();l];for i in 0..n{for j in 0..m{c[i+j]+=a[i]*b[j];}}c}}
        pub mod convolution_ntt_friendly {use crate::__cargo_equip::preludes::convolution_ntt_friendly::*;use convolution_naive::convolution_naive
            ;use modint::StaticModInt;pub fn ntt<const P:u32>(a:&mut[StaticModInt<P>]){assert!(StaticModInt::<P>::IS_NTT_FRIENDLY);let n=a.len
            ();assert_eq!(n.count_ones(),1);let h=n.trailing_zeros()as usize;let mut len=0;while len<h{if h-len==1{let p=1<<h-len-1;let mut rot
            =StaticModInt::raw(1);for s in 0..1<<len{let offset=s<<h-len;for i in 0..p{let l=a[i+offset];let r=a[i+offset+p]*rot;a[i+offset]=l+r;a[i
            +offset+p]=l-r;}if s+1!=1<<len{rot*=StaticModInt::raw(StaticModInt::<P>::RATE2[(!s).trailing_zeros()as usize]);}}len+=1;}else{let p=1<<h
            -len-2;let mut rot=StaticModInt::<P>::raw(1);let imag=StaticModInt::<P>::raw(StaticModInt::<P>::ROOT[2]);for s in 0..1<<len{let rot2=rot
            *rot;let rot3=rot2*rot;let offset=s<<h-len;for i in 0..p{let mod2=(StaticModInt::<P>::modulus()as u64).pow(2);let a0=a[i+offset].val()as 
            u64;let a1=a[i+offset+p].val()as u64*rot.val()as u64;let a2=a[i+offset+p*2].val()as u64*rot2.val()as u64;let a3=a[i+offset+p*3].val()as 
            u64*rot3.val()as u64;let a1na3imag=StaticModInt::<P>::from(a1+mod2-a3).val()as u64*imag.val()as u64;let na2=mod2-a2;a[i+offset]
            =StaticModInt::from(a0+a2+a1+a3);a[i+offset+p]=StaticModInt::from(a0+a2+(mod2*2-(a1+a3)));a[i+offset+p*2]=StaticModInt::from(a0+na2
            +a1na3imag);a[i+offset+p*3]=StaticModInt::from(a0+na2+mod2-a1na3imag);}if s+1!=1<<len{rot*=StaticModInt::raw(StaticModInt::<P>::RATE3[(!s
            ).trailing_zeros()as usize]);}}len+=2;}}}pub fn ntt_inv<const P:u32>(a:&mut[StaticModInt<P>]){assert!(StaticModInt::<P>::IS_NTT_FRIENDLY
            );let n=a.len();assert_eq!(n.count_ones(),1);let h=n.trailing_zeros()as usize;let mut len=h;while len>0{if len==1{let p=1<<h-len;let mut 
            irot=StaticModInt::<P>::raw(1);for s in 0..1<<len-1{let offset=s<<h-len+1;for i in 0..p{let l=a[i+offset];let r=a[i+offset+p];a[i+offset]
            =l+r;a[i+offset+p]=StaticModInt::<P>::from((StaticModInt::<P>::modulus()+l.val()-r.val())as u64*irot.val()as u64,);}if s+1!=1<<len-1{irot
            *=StaticModInt::<P>::raw(StaticModInt::<P>::IRATE2[(!s).trailing_zeros()as usize],);}}len-=1;}else{let p=1<<h-len;let mut irot
            =StaticModInt::<P>::raw(1);let iimag=StaticModInt::<P>::raw(StaticModInt::<P>::IROOT[2]);for s in 0..1<<len-2{let irot2=irot*irot;let 
            irot3=irot2*irot;let offset=s<<h-len+2;for i in 0..p{let a0=a[i+offset].val()as u64;let a1=a[i+offset+p].val()as u64;let a2=a[i+offset+p
            *2].val()as u64;let a3=a[i+offset+p*3].val()as u64;let a2na3iimag=StaticModInt::<P>::from((StaticModInt::<P>::modulus()as u64+a2-a3
            )*iimag.val()as u64,).val()as u64;a[i+offset]=StaticModInt::<P>::from(a0+a1+a2+a3);a[i+offset+p]=StaticModInt::<P>::from((a0
            +(StaticModInt::<P>::modulus()as u64-a1)+a2na3iimag)*irot.val()as u64,);a[i+offset+p*2]=StaticModInt::<P>::from((a0+a1+(StaticModInt::<P
            >::modulus()as u64-a2)+(StaticModInt::<P>::modulus()as u64-a3))*irot2.val()as u64,);a[i+offset+p*3]=StaticModInt::<P>::from((a0
            +(StaticModInt::<P>::modulus()as u64-a1)+(StaticModInt::<P>::modulus()as u64-a2na3iimag))*irot3.val()as u64,);}if s+1!=1<<len-2{irot
            *=StaticModInt::<P>::raw(StaticModInt::<P>::IRATE3[(!s).trailing_zeros()as usize],);}}len-=2;}}let inv_n=StaticModInt::<P>::new(n).inv
            ();for x in a.iter_mut(){*x*=inv_n;}}pub fn ntt_doubling<const P:u32>(a:&mut Vec<StaticModInt<P>>){let n=a.len();a.append(&mut a.clone
            ());ntt_inv(&mut a[n..]);let mut r=StaticModInt::new(1);let zeta=StaticModInt::new(StaticModInt::<P>::G).pow((P-1)as usize/(n<<1));for i 
            in n..n*2{a[i]*=r;r*=zeta;}ntt(&mut a[n..]);}pub fn convolution_ntt_friendly<const P:u32>(mut a:Vec<StaticModInt<P>>,mut b:Vec
            <StaticModInt<P>>,)->Vec<StaticModInt<P>>{let n=a.len();let m=b.len();if n==0||m==0{return vec![];}else if n.min(m)<=60{return 
            convolution_naive(&a,&b);}let len=n+m-1;let z=1<<64-(len-1).leading_zeros();a.resize(z,0.into());b.resize(z,0.into());ntt(&mut a);ntt
            (&mut b);for i in 0..z{a[i]*=b[i];}ntt_inv(&mut a);a.truncate(len);a}}
        pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros
            ::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate 
            core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std
            ::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T
            >{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F
            :FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false
            ,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T
            >{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate
            ::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;}
            ;}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub 
            use core::ops::Deref as __Deref;#[macro_export(local_inner_macros
            )]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty
            =$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($
            ($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref
            (&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!
            (LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn 
            initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations
            )]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N
            =$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros
            )]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt
            )*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt
            )*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e
            :expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt
            :tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn 
            initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod modint {use std::{fmt,hash::Hash,iter::{Product,Sum},num::ParseIntError,ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub
            ,SubAssign},str::FromStr,sync::atomic::{self,AtomicU32,AtomicU64},};#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent
            )]pub struct StaticModInt<const P:u32>(u32);#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]#[repr(transparent)]pub struct DynamicModInt
            (u32);pub type ModInt998244353=StaticModInt<998_244_353>;pub type ModInt1000000007=StaticModInt<1_000_000_007>;pub trait ModInt:Default
            +FromStr+From<i8>+From<i16>+From<i32>+From<i64>+From<i128>+From<isize>+From<u8>+From<u16>+From<u32>+From<u64>+From<u128>+From<usize>+Copy
            +Eq+Hash+fmt::Display+fmt::Debug+Neg<Output=Self>+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign
            +MulAssign+DivAssign{fn modulus()->u32;fn raw(val:u32)->Self;fn val(self)->u32;fn inv(self)->Self;fn pow(self,k:usize)->Self;fn sqrt(self
            )->Option<Self>;}const fn mul(x:u32,y:u32,m:u32)->u32{(x as u64*y as u64%m as u64)as u32}const fn pow(x:u32,mut n:u32,m:u32)->u32{if m
            ==1{return 0;}let mut r=1u64;let mut y=(x%m)as u64;while n!=0{if n&1!=0{r=r*y%m as u64;}y=y*y%m as u64;n>>=1;}r as u32}const fn is_prime
            (n:u32)->bool{match n{_ if n<=1=>return false,2|7|61=>return true,_ if n&1==0=>return false,_=>{}}let mut d=n-1;while d&1==0{d>>=1;}let a
            =[2,7,61];let mut i=0;while i<3{let mut t=d;let mut y=pow(a[i],t,n);while t!=n-1&&y!=1&&y!=n-1{y=(y as u64*y as u64%n as u64)as u32;t<<=1
            ;}if y!=n-1&&t&1==0{return false;}i+=1;}true}const fn extgcd(mut a:u32,b:u32)->(u32,u32){a=a%b;if a==0{return(b,0);}let mut s=b as i64
            ;let mut t=a as i64;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;let tmp=s;s=t;t=tmp;let tmp=m0;m0=m1;m1=tmp;}if m0
            <0{m0+=b as i64/s;}(s as u32,m0 as u32)}const fn primitive_root(m:u32)->u32{match m{2=>return 1,167_772_161=>return 3,469_762_049=>return 
            3,754_974_721=>return 11,998_244_353=>return 3,_=>{}}let mut divs=[0;20];divs[0]=2;let mut cnt=1;let mut x=(m-1)/2;while x%2==0{x/=2;}let 
            mut i=3;while i<std::u32::MAX{if i as u64*i as u64>x as u64{break;}if x%i==0{divs[cnt]=i;cnt+=1;while x%i==0{x/=i;}}i+=2;}if x
            >1{divs[cnt]=x;cnt+=1;}let mut g=2;loop{let mut i=0;while i<cnt{if pow(g,(m-1)/divs[i],m)==1{break;}i+=1;}if i==cnt{break g;}g+=1;}}const 
            fn ntt_info(m:u32,)->(u32,usize,[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],[u32;30],){let g=primitive_root(m);let rank2=(m-1
            ).trailing_zeros()as usize;let mut root=[0;30];let mut iroot=[0;30];let mut rate2=[0;30];let mut irate2=[0;30];let mut rate3=[0;30];let 
            mut irate3=[0;30];root[rank2]=pow(g,(m-1)>>rank2,m);iroot[rank2]=extgcd(root[rank2],m).1;let mut i=rank2;while i>0{i-=1;root[i]=mul
            (root[i+1],root[i+1],m);iroot[i]=mul(iroot[i+1],iroot[i+1],m);}let mut prod=1;let mut iprod=1;let mut i=0;while i+2<=rank2{rate2[i]=mul
            (root[i+2],prod,m);irate2[i]=mul(iroot[i+2],iprod,m);prod=mul(prod,iroot[i+2],m);iprod=mul(iprod,root[i+2],m);i+=1;}let mut prod=1;let 
            mut iprod=1;let mut i=0;while i+3<=rank2{rate3[i]=mul(root[i+3],prod,m);irate3[i]=mul(iroot[i+3],iprod,m);prod=mul(prod,iroot[i+3],m
            );iprod=mul(iprod,root[i+3],m);i+=1;}(g,rank2,root,iroot,rate2,irate2,rate3,irate3)}fn rat_convert(x:u64,m:u64,d:u64)->Option<(u64,u64
            )>{let n=m/(2*d);if x<n&&1<d{return Some((x,1));}let mut l=(0,1);let mut r=(1,0);loop{let num=l.0+r.0;let den=l.1+r.1;let(i,q)=match(num
            *m).cmp(&(den*x)){std::cmp::Ordering::Less=>{let k=(x*l.1-m*l.0-1)/(m*r.0-x*r.1);l.0+=k*r.0;l.1+=k*r.1;l}std::cmp::Ordering::Equal
            =>return None,std::cmp::Ordering::Greater=>{let k=(m*r.0-x*r.1-1)/(x*l.1-m*l.0);r.0+=k*l.0;r.1+=k*l.1;r}};if q*x<i*m{continue;}let p=q*x
            -i*m;if p<n&&q<d{return Some((p,q));}}}impl<const P:u32>ModInt for StaticModInt<P>{#[inline(always)]fn modulus()->u32{P}#[inline]fn raw
            (val:u32)->Self{Self(val)}#[inline]fn val(self)->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k
            )}fn sqrt(self)->Option<Self>{self.sqrt()}}impl<const P:u32>StaticModInt<P>{#[inline]pub fn new<T:Into<StaticModInt<P>>>(x:T)->Self{x
            .into()}#[inline(always)]pub fn modulus()->u32{P}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self
            .0}#[inline]pub fn inv(self)->Self{assert_ne!(self.0,0);self.pow(P as usize-2)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self
            ::from(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val
            ()<2{return Some(self);}else if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b
            +=1;}let mut e=(p-1).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m
            );while y.val()!=1{let mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}}impl ModInt for 
            DynamicModInt{#[inline(always)]fn modulus()->u32{BARRETT.modulus()}#[inline]fn raw(val:u32)->Self{Self(val)}#[inline]fn val(self
            )->u32{self.0}#[inline]fn inv(self)->Self{self.inv()}fn pow(self,k:usize)->Self{self.pow(k)}fn sqrt(self)->Option<Self>{self.sqrt()}}impl 
            DynamicModInt{#[inline]pub fn new<T:Into<DynamicModInt>>(x:T)->Self{x.into()}#[inline(always)]pub fn modulus()->u32{BARRETT.modulus
            ()}#[inline]pub fn raw(val:u32)->Self{Self(val)}#[inline]pub fn val(self)->u32{self.0}#[inline]pub fn inv(self)->Self{let(g,x)=extgcd
            (self.0,Self::modulus());assert_eq!(g,1);Self(x)}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::from(1);while k!=0{if k&1!
            =0{res*=self;}k>>=1;self*=self;}res}pub fn sqrt(self)->Option<Self>{let p=Self::modulus()as usize;if self.val()<2{return Some(self);}else 
            if self.pow(p-1>>1).val()!=1{return None;}let mut b=Self::from(1);while b.pow((p-1>>1)as usize).val()==1{b+=1;}let mut e=(p-1
            ).trailing_zeros()as usize;let m=(p-1)>>e;let mut x=self.pow(m-1>>1);let mut y=self*x*x;x*=self;let mut z=b.pow(m);while y.val()!=1{let 
            mut j=0;let mut t=y;while t.val()!=1{j+=1;t*=t;}z=z.pow(1<<e-j-1);x*=z;z*=z;y*=z;e=j;}Some(x)}pub fn set_modulus(modulus:u32){BARRETT.set
            (modulus)}}struct Barrett{m:AtomicU32,im:AtomicU64,}impl Barrett{const fn new(m:u32)->Self{Self{m:AtomicU32::new(m),im:AtomicU64::new((!0
            /m as u64).wrapping_add(1)),}}#[inline]fn set(&self,m:u32){let im=(!0/m as u64).wrapping_add(1);self.m.store(m,atomic::Ordering::SeqCst
            );self.im.store(im,atomic::Ordering::SeqCst);}#[inline]fn modulus(&self)->u32{self.m.load(atomic::Ordering::SeqCst)}#[inline]fn mul(&self
            ,a:u32,b:u32)->u32{let m=self.m.load(atomic::Ordering::SeqCst);let im=self.im.load(atomic::Ordering::SeqCst);let mut z=a as u64;z*=b as 
            u64;let x=(((z as u128)*(im as u128))>>64)as u64;let mut v=z.wrapping_sub(x.wrapping_mul(m as u64))as u32;if m<=v{v=v.wrapping_add(m
            );}v}}static BARRETT:Barrett=Barrett::new(998_244_353);impl<const P:u32>FromStr for StaticModInt<P>{type Err=ParseIntError;fn from_str(s
            :&str)->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl FromStr for DynamicModInt{type Err=ParseIntError;fn from_str(s:&str
            )->Result<Self,Self::Err>{s.parse::<i64>().map(Self::from)}}impl<const P:u32>fmt::Display for StaticModInt<P>{fn fmt(&self,f:&mut fmt
            ::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0)}}impl fmt::Display for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt
            ::Result{write!(f,"{}",self.0)}}impl<const P:u32>fmt::Debug for StaticModInt<P>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{if 
            let Some((num,den))=rat_convert(self.0 as u64,P as u64,1025){write!(f,"{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else if let Some((num
            ,den))=rat_convert((P-self.0)as u64,P as u64,1025){write!(f,"-{}",num)?;if den!=1{write!(f,"/{}",den)?;}}else{write!(f,"{}",self.0)?;}Ok
            (())}}impl fmt::Debug for DynamicModInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"{}",self.0
            )}}macro_rules!impl_from_integer{($(($t1:ty,$t2:ty)),*)=>{$(impl<const P:u32>From<$t1>for StaticModInt<P>{fn from(x:$t1)->Self{Self((x 
            as$t2).rem_euclid(P as$t2)as u32)}}impl From<$t1>for DynamicModInt{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(Self::modulus()as$t2)as 
            u32)}})*};}impl_from_integer!((i8,i32),(i16,i32),(i32,i32),(i64,i64),(isize,i64),(i128,i128),(u8,u32),(u16,u32),(u32,u32),(u64,u64
            ),(usize,u64),(u128,u128));impl<const P:u32,T:Into<Self>>AddAssign<T>for StaticModInt<P>{fn add_assign(&mut self,rhs:T){self.0+=rhs.into
            ().0;if self.0>=P{self.0-=P;}}}impl<T:Into<Self>>AddAssign<T>for DynamicModInt{fn add_assign(&mut self,rhs:T){self.0+=rhs.into().0;if 
            self.0>=Self::modulus(){self.0-=Self::modulus();}}}impl<const P:u32,T:Into<Self>>SubAssign<T>for StaticModInt<P>{fn sub_assign(&mut self
            ,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=P;}self.0-=rhs;}}impl<T:Into<Self>>SubAssign<T>for DynamicModInt{fn sub_assign(&mut 
            self,rhs:T){let rhs=rhs.into().0;if self.0<rhs{self.0+=Self::modulus();}self.0-=rhs;}}impl<const P:u32,T:Into<Self>>MulAssign<T>for 
            StaticModInt<P>{fn mul_assign(&mut self,rhs:T){*self=Self((self.0 as u64*rhs.into().0 as u64%P as u64)as u32);}}impl<T:Into<Self
            >>MulAssign<T>for DynamicModInt{fn mul_assign(&mut self,rhs:T){*self=Self(BARRETT.mul(self.0,rhs.into().0));}}impl<const P:u32,T:Into
            <Self>>DivAssign<T>for StaticModInt<P>{fn div_assign(&mut self,rhs:T){*self*=rhs.into().inv()}}impl<T:Into<Self>>DivAssign<T>for 
            DynamicModInt{fn div_assign(&mut self,rhs:T){*self=*self*rhs.into().inv()}}impl<const P:u32>Neg for StaticModInt<P>{type Output=Self;fn 
            neg(self)->Self::Output{if self.0==0{Self(0)}else{Self(P-self.0)}}}impl Neg for DynamicModInt{type Output=Self;fn neg(self)->Self
            ::Output{if self.0==0{Self(0)}else{Self(Self::modulus()-self.0)}}}impl<const P:u32>Neg for&StaticModInt<P>{type Output=StaticModInt<P>;fn 
            neg(self)->Self::Output{if self.0==0{StaticModInt(0)}else{StaticModInt(P-self.0)}}}impl Neg for&DynamicModInt{type Output=DynamicModInt
            ;fn neg(self)->Self::Output{if self.0==0{DynamicModInt(0)}else{DynamicModInt(DynamicModInt::modulus()-self.0)}}}macro_rules!impl_ops{($
            ($trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl<const P:u32>$trait_assign<&StaticModInt<P>>for StaticModInt<P
            >{fn$fn_assign(&mut self,rhs:&StaticModInt<P>){self.$fn_assign(*rhs);}}impl<const P:u32,T:Into<StaticModInt<P>>>$trait<T>for StaticModInt
            <P>{type Output=StaticModInt<P>;fn$fn(mut self,rhs:T)->Self::Output{self.$fn_assign(rhs.into());self}}impl<const P:u32>$trait
            <&StaticModInt<P>>for StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P>)->Self::Output{self.$fn(*rhs)}}impl
            <const P:u32,T:Into<StaticModInt<P>>>$trait<T>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:T)->Self::Output{(*self).$fn
            (rhs.into())}}impl<const P:u32>$trait<&StaticModInt<P>>for&StaticModInt<P>{type Output=StaticModInt<P>;fn$fn(self,rhs:&StaticModInt<P
            >)->Self::Output{(*self).$fn(*rhs)}}impl$trait_assign<&DynamicModInt>for DynamicModInt{fn$fn_assign(&mut self,rhs:&DynamicModInt){self
            .$fn_assign(*rhs);}}impl<T:Into<DynamicModInt>>$trait<T>for DynamicModInt{type Output=DynamicModInt;fn$fn(mut self,rhs:T)->Self
            ::Output{self.$fn_assign(rhs.into());self}}impl$trait<&DynamicModInt>for DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs
            :&DynamicModInt)->Self::Output{self.$fn(*rhs)}}impl<T:Into<DynamicModInt>>$trait<T>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self
            ,rhs:T)->Self::Output{(*self).$fn(rhs.into())}}impl$trait<&DynamicModInt>for&DynamicModInt{type Output=DynamicModInt;fn$fn(self,rhs
            :&DynamicModInt)->Self::Output{(*self).$fn(*rhs)}})*};}impl_ops!{Add,AddAssign,add,add_assign,Sub,SubAssign,sub,sub_assign,Mul,MulAssign
            ,mul,mul_assign,Div,DivAssign,div,div_assign,}impl<const P:u32>Sum for StaticModInt<P>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{iter
            .fold(Self::raw(0),|b,x|b+x)}}impl<const P:u32>Product for StaticModInt<P>{fn product<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self
            ::from(1),|b,x|b*x)}}impl<'a,const P:u32>Sum<&'a Self>for StaticModInt<P>{fn sum<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self
            ::raw(0),|b,x|b+x)}}impl<'a,const P:u32>Product<&'a Self>for StaticModInt<P>{fn product<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter
            .fold(Self::from(1),|b,x|b*x)}}impl<const P:u32>StaticModInt<P>{pub const G:u32=ntt_info(P).0;pub const RANK2:usize=ntt_info(P).1;pub 
            const ROOT:[u32;30]=ntt_info(P).2;pub const IROOT:[u32;30]=ntt_info(P).3;pub const RATE2:[u32;30]=ntt_info(P).4;pub const IRATE2:[u32;30]
            =ntt_info(P).5;pub const RATE3:[u32;30]=ntt_info(P).6;pub const IRATE3:[u32;30]=ntt_info(P).7;pub const IS_NTT_FRIENDLY:bool=is_prime(P
            )&&Self::RANK2>=21;}}<hide>
        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 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 std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub 
            struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R
            >{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable
            (),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){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.current_context=line.into_boxed_str();self.tokens
            =unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for 
            LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self
            .tokens.peek().is_none()}}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 std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct 
            OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_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.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read
            :PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable
            ();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self
            )->bool{self.tokens.peek().is_none()}}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()))}}}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>;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;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use 
            std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref 
            STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin
            ())));}#[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.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_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 crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.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(crate) mod macros {
        pub mod __convolution_naive_0_1_0 {}
        pub mod convolution_ntt_friendly {}
        pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create
            ,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal
            ,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
        pub mod modint {}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value}
            ;}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}
    mod preludes {
        pub mod __convolution_naive_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::modint;}
        pub mod convolution_ntt_friendly {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__convolution_naive_0_1_0 as 
            convolution_naive,modint};}
        pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
        pub mod modint {}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate
            ::__cargo_equip::crates::__lazy_static_1_4_0 as lazy_static;}
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0