// ---------- begin recurse ---------- // reference // https://twitter.com/noshi91/status/1393952665566994434 // https://twitter.com/shino16_cp/status/1393933468082397190 pub fn recurse(f: F) -> impl Fn(A) -> R where F: Fn(&dyn Fn(A) -> R, A) -> R, { fn call(f: &F, a: A) -> R where F: Fn(&dyn Fn(A) -> R, A) -> R, { f(&|a| call(f, a), a) } move |a| call(&f, a) } // ---------- end recurse ---------- use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub struct ConstantModulo; impl Modulo for ConstantModulo<{ M }> { fn modulo() -> u32 { M } } pub struct ModInt(u32, PhantomData); impl Clone for ModInt { fn clone(&self) -> Self { Self::new_unchecked(self.0) } } impl Copy for ModInt {} impl Add for ModInt { type Output = ModInt; fn add(self, rhs: Self) -> Self::Output { let mut v = self.0 + rhs.0; if v >= T::modulo() { v -= T::modulo(); } Self::new_unchecked(v) } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = ModInt; fn sub(self, rhs: Self) -> Self::Output { let mut v = self.0 - rhs.0; if self.0 < rhs.0 { v += T::modulo(); } Self::new_unchecked(v) } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = ModInt; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; Self::new_unchecked(v as u32) } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { if self.is_zero() { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::fmt::Debug for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> ModInt { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl From for ModInt { fn from(val: u64) -> ModInt { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl From for ModInt { fn from(val: i64) -> ModInt { if val >= 0 { ModInt::from(val as u64) } else { -ModInt::from((-val) as u64) } } } impl ModInt { pub fn new_unchecked(n: u32) -> Self { ModInt(n, PhantomData) } pub fn zero() -> Self { ModInt::new_unchecked(0) } pub fn one() -> Self { ModInt::new_unchecked(1) } pub fn is_zero(&self) -> bool { self.0 == 0 } } impl ModInt { pub fn new(d: u32) -> Self { ModInt::new_unchecked(d % T::modulo()) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(!self.is_zero()); self.pow(T::modulo() as u64 - 2) } } type M = ModInt>; fn read() -> (usize, usize) { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let a = s .trim() .split_whitespace() .flat_map(|s| s.parse::()) .collect::>(); (a[0], a[1]) } fn calc(h: usize, w: usize, f: F, g: G) -> M where F: Fn(usize, usize) -> M, G: Fn(usize, usize) -> M, { assert!(h <= w); use std::cell::*; let memo = RefCell::new(std::collections::HashMap::<(usize, usize), M>::new()); let res = recurse(|rec, (h, w): (usize, usize)| -> M { if let Some(v) = memo.borrow().get(&(h, w)) { return *v; } let mut ans = f(h, w); let mut l = 2; while l <= h { let r = std::cmp::min(h / (h / l), w / (w / l)); ans -= g(l, r) * rec((h / l, w / l)); l = r + 1; } memo.borrow_mut().insert((h, w), ans); ans })((h, w)); res } fn gcd(a: usize, b: usize) -> usize { if b == 0 { a } else { gcd(b, a % b) } } // 1 <= dx < H, 1 <= dy < W, gcd(dx, dy) == 1 // となるようなdx, dy について // (H - dx)(W - dy) の和 // fn run() { let (h, w) = read(); let mut ans = M::from(h * (w - 1) + w * (h - 1)); if h > 1 && w > 1 { let (h, w) = (h.min(w), h.max(w)); let inv6 = M::new(6).inv(); let two = |n: usize| -> M { M::from(n * (n + 1)) * M::from(2 * n + 1) * inv6 }; let one = |n: usize| -> M { M::from(n * (n + 1) / 2) }; let mut add = M::zero(); add += M::from(h * w) * calc(h - 1, w - 1, |h, w| M::from(h * w), |l, r| M::from(r - l + 1)); add -= M::from(w) * calc(h - 1, w - 1, |h, w| M::from(w) * one(h), |l, r| one(r) - one(l - 1)); add -= M::from(h) * calc(h - 1, w - 1, |h, w| M::from(h) * one(w), |l, r| one(r) - one(l - 1)); add += calc(h - 1, w - 1, |h, w| one(h) * one(w), |l, r| two(r) - two(l - 1)); ans += add + add; } println!("{}", ans); } fn main() { run(); }