use std::io::Read; fn get_word() -> String { let stdin = std::io::stdin(); let mut stdin=stdin.lock(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get() -> T { get_word().parse().ok().unwrap() } fn factorize(mut x: i64) -> Vec<(i64, usize)> { let mut p = 2; let mut ans = vec![]; while p * p <= x { let mut e = 0; while x % p == 0 { x /= p; e += 1; } if e > 0 { ans.push((p, e)); } p += 1; } if x > 1 { ans.push((x, 1)); } ans } fn dfs(v: usize, pe: &[(i64, usize)], mut x: i64, mut phi: i64, ans: &mut Vec<(i64, i64)>) { if v >= pe.len() { ans.push((x, phi)); return; } let (p, e) = pe[v]; dfs(v + 1, pe, x, phi, ans); x /= p; phi *= p - 1; for _ in 0..e { dfs(v + 1, pe, x, phi, ans); x /= p; phi *= p; } } fn get_divs_and_phis(x: i64) -> Vec<(i64, i64)> { let pe = factorize(x); let mut ans = vec![]; dfs(0, &pe, x, 1, &mut ans); ans } fn powmod(x: i64, mut e: i64) -> i64 { let mut sum = 1; let mut cur = x % MOD; while e > 0 { if e % 2 != 0 { sum = sum * cur % MOD; } cur = cur * cur % MOD; e /= 2; } sum } const MOD: i64 = 1_000_000_007; fn main() { let h: i64 = get(); let w: i64 = get(); let k: i64 = get(); let hpe = get_divs_and_phis(h); let wpe = get_divs_and_phis(w); let mut ans = 0; for &(a, phi1) in &hpe { for &(b, phi2) in &wpe { let mut tmp = powmod(k, a * b); tmp = tmp * phi1 % MOD; tmp = tmp * phi2 % MOD; ans = (ans + tmp) % MOD; } } println!("{}", ans); }