use proconio::input; use std::ops::Add; use std::ops::Mul; use std::ops::Sub; type Fp = fp::Fp<1000000007>; fn main() { input! { n: usize, a: [u64; n + 1], b: [u64; n + 1], } let a = a.iter().map(|&x| Fp::new(x)).collect::>(); let b = b.iter().map(|&x| Fp::new(x)).collect::>(); let c = karatsuba(a, b); let ans = c[..=n].iter().sum::(); println!("{}", ans); } trait Zero { fn zero() -> Self; } impl Zero for Fp { fn zero() -> Self { Fp::new(0) } } fn karatsuba(mut a: Vec, mut b: Vec) -> Vec where T: Clone + Copy + Mul + Add + Sub + Zero + std::fmt::Debug, { let len = a.len() + b.len() - 1; let n = a.len().max(b.len()).max(2).next_power_of_two(); a.resize(n, T::zero()); b.resize(n, T::zero()); let mut src = (0..n).flat_map(|i| [a[i], b[i]]).collect::>(); src.reserve(4 * n); let mut tar = Vec::with_capacity(2 * n); let mut tertiary = n * n; while tertiary != 0 { for size in (0..(tertiary.trailing_zeros() as usize) / 2) .rev() .map(|i| 1 << i) { let size = size * 2; for (i, j) in (src.len() - 2 * size..).zip(src.len() - size..src.len()) { src.push(src[i] + src[j]); } } tar.extend([src.pop().unwrap() * src.pop().unwrap(), T::zero()]); tertiary -= 1; for i in 0.. { if tertiary >> (2 * i) & 3 != 3 { break; } tertiary ^= 1 << (2 * i); } for size in (0..((tertiary.trailing_zeros() as usize) / 2).min(n.trailing_zeros() as usize)) .map(|i| 1 << i) { for ((i, j), k) in (tar.len() - 6 * size..) .zip(tar.len() - 4 * size..) .zip(tar.len() - 2 * size..tar.len()) { let (x, y, z) = (tar[i], tar[j], tar[k]); (tar[i], tar[j], tar[k]) = (z, y, x - y - z); } for (i, j) in (tar.len() - 5 * size..).zip(tar.len() - 2 * size..tar.len()) { tar[i] = tar[i] + tar[j]; } tar.truncate(tar.len() - 2 * size); } } tar.truncate(len); tar } // fp {{{ // https://ngtkana.github.io/ac-adapter-rs/fp/index.html #[allow(dead_code)] mod fp { mod ext_gcd { pub(crate) fn mod_inv(x: u64) -> u64 { debug_assert!(P % 2 == 1); debug_assert!(P < 1 << 31); debug_assert!(x < P); mod_inv_signed(x as i64, P as i64) as u64 } fn mod_inv_signed(a: i64, m: i64) -> i64 { debug_assert!(a > 0); debug_assert!(m > 0); if a == 1 { return 1; } m + (1 - m * mod_inv_signed(m % a, a)) / a } } mod factorial { use super::Fp; use std::ops::Index; pub struct Factorial { fact: Vec>, inv_fact: Vec>, } impl Factorial

{ pub fn new(length: usize) -> Self { let mut fact = vec![Fp::

::new(1); length + 1]; let mut inv_fact = vec![Fp::

::new(1); length + 1]; for i in 1..=length { fact[i] = fact[i - 1] * Fp::

::new(i as u64); } inv_fact[length] = fact[length].inv(); for i in (1..=length).rev() { inv_fact[i - 1] = inv_fact[i] * Fp::

::new(i as u64); } Self { fact, inv_fact } } pub fn fact(&self, n: usize) -> Fp

{ self.fact[n] } pub fn inv_fact(&self, n: usize) -> Fp

{ self.inv_fact[n] } pub fn perm(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] } pub fn comb(&self, n: usize, k: usize) -> Fp

{ self.fact[n] * self.inv_fact[n - k] * self.inv_fact[k] } pub fn binom(&self, n: usize, k: usize) -> Fp

{ self.comb(n, k) } pub fn comb_or_zero(&self, n: usize, k: isize) -> Fp

{ if k < 0 || k as usize > n { Fp::

::new(0) } else { self.comb(n, k as usize) } } pub fn comb_with_reputation(&self, n: usize, k: usize) -> Fp

{ assert!(n > 0 || k > 0); self.comb(n + k - 1, k) } } impl Index for Factorial

{ type Output = Fp

; fn index(&self, index: usize) -> &Self::Output { &self.fact[index] } } } mod fourier { use super::mod_inv; use super::Fp; use super::PrimitiveRoot; const P1: u64 = 924844033; const P2: u64 = 998244353; const P3: u64 = 1012924417; type F1 = Fp; type F2 = Fp; type F3 = Fp; pub fn fps_mul(a: impl AsRef<[Fp

]>, b: impl AsRef<[Fp

]>) -> Vec> where (): PrimitiveRoot

, { let a = a.as_ref(); let b = b.as_ref(); if a.is_empty() || b.is_empty() { return vec![]; } let mut a = a.to_vec(); let mut b = b.to_vec(); let n = a.len() + b.len() - 1; let len = n.next_power_of_two(); a.resize(len, Fp::new(0)); b.resize(len, Fp::new(0)); fft(&mut a); fft(&mut b); for (a, b) in a.iter_mut().zip(b.iter()) { *a *= *b; } ifft(&mut a); a.truncate(n); a } pub fn any_mod_fps_mul(a: &[Fp

], b: &[Fp

]) -> Vec> { let v1 = fps_mul( a.iter().map(|&x| F1::new(x.value())).collect::>(), b.iter().map(|&x| F1::new(x.value())).collect::>(), ); let v2 = fps_mul( a.iter().map(|&x| F2::new(x.value())).collect::>(), b.iter().map(|&x| F2::new(x.value())).collect::>(), ); let v3 = fps_mul( a.iter().map(|&x| F3::new(x.value())).collect::>(), b.iter().map(|&x| F3::new(x.value())).collect::>(), ); v1.into_iter() .zip(v2) .zip(v3) .map(|((e1, e2), e3)| garner(e1, e2, e3)) .collect::>() } pub fn fft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); assert!((P - 1) % n as u64 == 0); let mut root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4); let mut fft_len = n; while 4 <= fft_len { let quarter = fft_len / 4; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + f[k]; let y = f[j] + f[l]; let z = f[i] - f[k]; let w = fourth * (f[j] - f[l]); f[i] = x + y; f[j] = c2 * (x - y); f[k] = c * (z + w); f[l] = c2 * c * (z - w); c *= root; } } root *= root; root *= root; fft_len = quarter; } if fft_len == 2 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } } } pub fn ifft(f: &mut [Fp

]) where (): PrimitiveRoot

, { let n = f.len(); assert!(n.is_power_of_two()); let root = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / f.len() as u64); let mut roots = std::iter::successors(Some(root.inv()), |x| Some(x * x)) .take(n.trailing_zeros() as usize + 1) .collect::>(); roots.reverse(); let fourth = <() as PrimitiveRoot

>::VALUE.pow((P - 1) / 4).inv(); let mut quarter = 1_usize; if n.trailing_zeros() % 2 == 1 { for f in f.chunks_mut(2) { let x = f[0]; let y = f[1]; f[0] = x + y; f[1] = x - y; } quarter = 2; } while quarter != n { let fft_len = quarter * 4; let root = roots[fft_len.trailing_zeros() as usize]; for f in f.chunks_mut(fft_len) { let mut c = Fp::new(1); for (((i, j), k), l) in (0..) .zip(quarter..) .zip(quarter * 2..) .zip(quarter * 3..) .take(quarter) { let c2 = c * c; let x = f[i] + c2 * f[j]; let y = f[i] - c2 * f[j]; let z = c * (f[k] + c2 * f[l]); let w = fourth * c * (f[k] - c2 * f[l]); f[i] = x + z; f[j] = y + w; f[k] = x - z; f[l] = y - w; c *= root; } } quarter = fft_len; } let d = Fp::from(f.len()).inv(); f.iter_mut().for_each(|x| *x *= d); } fn garner(x1: Fp, x2: Fp, x3: Fp) -> Fp

{ let (x1, x2, x3) = (x1.value(), x2.value(), x3.value()); let x2 = ((x2 + (P2 - x1)) * mod_inv::(P1)) % P2; let x3 = (((x3 + (P3 - x1)) * mod_inv::(P1) % P3 + (P3 - x2)) * mod_inv::(P2)) % P3; Fp::new(x1 + P1 * (x2 + P2 * x3 % P)) } } use ext_gcd::mod_inv; pub use factorial::Factorial; pub use fourier::any_mod_fps_mul; pub use fourier::fft; pub use fourier::fps_mul; pub use fourier::ifft; use std::iter::Product; use std::iter::Sum; use std::mem::swap; use std::ops::Add; use std::ops::AddAssign; use std::ops::Div; use std::ops::DivAssign; use std::ops::Mul; use std::ops::MulAssign; use std::ops::Neg; use std::ops::Sub; use std::ops::SubAssign; #[macro_export] macro_rules! fp { ($value:expr) => { $crate::fp::Fp::from($value) }; ($value:expr; mod $p:expr) => { $crate::fp::Fp::<$p>::from($value) }; } pub trait PrimitiveRoot { const VALUE: Fp

; } impl PrimitiveRoot<998244353> for () { const VALUE: Fp<998244353> = Fp::new(3); } impl PrimitiveRoot<1012924417> for () { const VALUE: Fp<1012924417> = Fp::new(5); } impl PrimitiveRoot<924844033> for () { const VALUE: Fp<924844033> = Fp::new(5); } #[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct Fp { value: u64, } impl Fp

{ pub const fn new(value: u64) -> Self { Self { value: value % P } } pub const fn value(self) -> u64 { self.value } pub fn inv(self) -> Self { Self { value: mod_inv::

(self.value), } } pub fn pow(self, mut exp: u64) -> Self { let mut result = Self::new(1); let mut base = self; while exp > 0 { if exp & 1 == 1 { result *= base; } base *= base; exp >>= 1; } result } pub fn sign(pow: usize) -> Self { Self::new(if pow % 2 == 0 { 1 } else { P - 1 }) } } impl std::fmt::Debug for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { pub fn berlekamp_massey_fp(a: i64, p: i64) -> [i64; 2] { let mut u0 = 0_i64; let mut v0 = 1_i64; let mut w0 = a * u0 + p * v0; let mut u1 = 1_i64; let mut v1 = 0_i64; let mut w1 = a * u1 + p * v1; while p <= w0 * w0 { let q = w0 / w1; u0 -= q * u1; v0 -= q * v1; w0 -= q * w1; swap(&mut u0, &mut u1); swap(&mut v0, &mut v1); swap(&mut w0, &mut w1); } [w0, u0] } if self.value == 0 { return write!(f, "0"); } let [mut num, mut den] = berlekamp_massey_fp(self.value as i64, P as i64); if den < 0 { num = -num; den = -den; } if den == 1 { write!(f, "{}", num) } else { write!(f, "{}/{}", num, den) } } } impl std::fmt::Display for Fp

{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.value()) } } macro_rules! impl_from_signed { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { if x < 0 { -Self::new((P as i64 - x as i64) as u64) } else { Self::new(x as u64) } } } )* }; } impl_from_signed!(i8, i16, i32, i64, i128, isize); macro_rules! impl_from_unsigned { ($($t:ty),*) => { $( impl From<$t> for Fp

{ fn from(x: $t) -> Self { Self::new(x as u64) } } )* }; } impl_from_unsigned!(u8, u16, u32, u64, u128, usize); impl AddAssign> for Fp

{ fn add_assign(&mut self, rhs: Fp

) { self.value += rhs.value; if self.value >= P { self.value -= P; } } } impl SubAssign> for Fp

{ fn sub_assign(&mut self, rhs: Fp

) { if self.value < rhs.value { self.value += P; } self.value -= rhs.value; } } impl MulAssign> for Fp

{ fn mul_assign(&mut self, rhs: Fp

) { self.value = self.value * rhs.value % P; } } #[allow(clippy::suspicious_op_assign_impl)] impl DivAssign> for Fp

{ fn div_assign(&mut self, rhs: Fp

) { *self *= rhs.inv() } } macro_rules! fp_forward_ops { ($( $trait:ident, $trait_assign:ident, $fn:ident, $fn_assign:ident, )*) => {$( impl $trait_assign<&Fp

> for Fp

{ fn $fn_assign(&mut self, rhs: &Fp

) { self.$fn_assign(*rhs); } } impl>> $trait for Fp

{ type Output = Fp

; fn $fn(mut self, rhs: T) -> Self::Output { self.$fn_assign(rhs.into()); self } } impl $trait<&Fp

> for Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { self.$fn(*rhs) } } impl>> $trait for &Fp

{ type Output = Fp

; fn $fn(self, rhs: T) -> Self::Output { (*self).$fn(rhs.into()) } } impl $trait<&Fp

> for &Fp

{ type Output = Fp

; fn $fn(self, rhs: &Fp

) -> Self::Output { (*self).$fn(*rhs) } } )*}; } fp_forward_ops! { Add, AddAssign, add, add_assign, Sub, SubAssign, sub, sub_assign, Mul, MulAssign, mul, mul_assign, Div, DivAssign, div, div_assign, } impl Neg for Fp

{ type Output = Fp

; fn neg(mut self) -> Self::Output { if self.value > 0 { self.value = P - self.value; } self } } impl Sum for Fp

{ fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |acc, x| acc + x) } } impl<'a, const P: u64> Sum<&'a Self> for Fp

{ fn sum>(iter: I) -> Self { iter.copied().sum() } } impl Product for Fp

{ fn product>(iter: I) -> Self { iter.fold(Self::new(1), |acc, x| acc * x) } } impl<'a, const P: u64> Product<&'a Self> for Fp

{ fn product>(iter: I) -> Self { iter.copied().product() } } } // }}}