#![allow(unused_imports)] #![allow(non_snake_case, unused)] use std::cmp::*; use std::collections::*; use std::ops::*; use std::marker::*; use proconio::*; use proconio::marker::*; const INF: i64 = std::i64::MAX/100; const MOD: i64 = 1_000_000_007; // const MOD: i64 = 998_244_353; // https://yukicoder.me/submissions/585145 より // ---------- begin ModInt ---------- mod modint { #[allow(dead_code)] pub struct Mod; impl ConstantModulo for Mod { const MOD: u32 = 1_000_000_007; } #[allow(dead_code)] pub struct StaticMod; static mut STATIC_MOD: u32 = 0; impl Modulo for StaticMod { fn modulo() -> u32 { unsafe { STATIC_MOD } } } #[allow(dead_code)] impl StaticMod { pub fn set_modulo(p: u32) { unsafe { STATIC_MOD = p; } } } use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub trait ConstantModulo { const MOD: u32; } impl<T> Modulo for T where T: ConstantModulo, { fn modulo() -> u32 { T::MOD } } pub struct ModInt<T>(pub u32, PhantomData<T>); impl<T> Clone for ModInt<T> { fn clone(&self) -> Self { ModInt::new_unchecked(self.0) } } impl<T> Copy for ModInt<T> {} impl<T: Modulo> Add for ModInt<T> { type Output = ModInt<T>; fn add(self, rhs: Self) -> Self::Output { let mut d = self.0 + rhs.0; if d >= T::modulo() { d -= T::modulo(); } ModInt::new_unchecked(d) } } impl<T: Modulo> AddAssign for ModInt<T> { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl<T: Modulo> Sub for ModInt<T> { type Output = ModInt<T>; fn sub(self, rhs: Self) -> Self::Output { let mut d = T::modulo() + self.0 - rhs.0; if d >= T::modulo() { d -= T::modulo(); } ModInt::new_unchecked(d) } } impl<T: Modulo> SubAssign for ModInt<T> { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl<T: Modulo> Mul for ModInt<T> { type Output = ModInt<T>; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; ModInt::new_unchecked(v as u32) } } impl<T: Modulo> MulAssign for ModInt<T> { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl<T: Modulo> Neg for ModInt<T> { type Output = ModInt<T>; fn neg(self) -> Self::Output { if self.0 == 0 { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl<T> std::fmt::Display for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl<T: Modulo> std::str::FromStr for ModInt<T> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let val = s.parse::<u32>()?; Ok(ModInt::new(val)) } } impl<T: Modulo> From<usize> for ModInt<T> { fn from(val: usize) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl<T: Modulo> From<u64> for ModInt<T> { fn from(val: u64) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl<T: Modulo> From<i64> for ModInt<T> { fn from(val: i64) -> ModInt<T> { let m = T::modulo() as i64; ModInt::new((val % m + m) as u32) } } #[allow(dead_code)] impl<T> ModInt<T> { pub fn new_unchecked(d: u32) -> Self { ModInt(d, 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 } } #[allow(dead_code)] impl<T: Modulo> ModInt<T> { 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.0 != 0); self.pow(T::modulo() as u64 - 2) } } #[allow(dead_code)] pub fn mod_pow(r: u64, mut n: u64, m: u64) -> u64 { let mut t = 1 % m; let mut s = r % m; while n > 0 { if n & 1 == 1 { t = t * s % m; } s = s * s % m; n >>= 1; } t } } // ---------- end ModInt ---------- // ---------- begin Precalc ---------- mod precalc { use super::modint::*; #[allow(dead_code)] pub struct Precalc<T> { inv: Vec<ModInt<T>>, fact: Vec<ModInt<T>>, ifact: Vec<ModInt<T>>, } #[allow(dead_code)] impl<T: Modulo> Precalc<T> { pub fn new(n: usize) -> Precalc<T> { let mut inv = vec![ModInt::one(); n + 1]; let mut fact = vec![ModInt::one(); n + 1]; let mut ifact = vec![ModInt::one(); n + 1]; for i in 2..(n + 1) { fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32); } ifact[n] = fact[n].inv(); if n > 0 { inv[n] = ifact[n] * fact[n - 1]; } for i in (1..n).rev() { ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32); inv[i] = ifact[i] * fact[i - 1]; } Precalc { inv: inv, fact: fact, ifact: ifact, } } pub fn inv(&self, n: usize) -> ModInt<T> { assert!(n > 0); self.inv[n] } pub fn fact(&self, n: usize) -> ModInt<T> { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt<T> { self.ifact[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt<T> { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn comb(&self, n: usize, k: usize) -> ModInt<T> { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } } // ---------- end Precalc ---------- use modint::*; type M = ModInt<Mod>; struct SieveOfEratosthenes { primes: Vec<usize>, divs: Vec<usize>, mobius: Vec<i64>, } impl SieveOfEratosthenes { pub fn new(n: usize) -> Self { let mut divs = vec![1;n+1]; let mut mobius = vec![-1;n+1]; for i in 2..=n { if divs[i]!=1 { continue; } for j in 1..=n { let val = i*j; if val>n { break; } divs[val as usize] = i; if (val/i)%i==0 { mobius[val as usize] = 0; } else { mobius[val as usize] = -mobius[val as usize]; } } } let mut primes = divs.iter() .enumerate() .filter(|x| *x.1>1 && x.0==*x.1) .map(|x| *x.1) .collect::<Vec<usize>>(); SieveOfEratosthenes { divs, primes, mobius, } } pub fn factors(&self, n: usize) -> Vec<(usize,usize)> { assert!(n+1<=self.divs.len()); let mut ans = vec![]; let mut x = n; while x > 1 { let nxt = self.divs[x]; ans.push(nxt); x /= nxt; } let mut map = HashMap::<usize,usize>::new(); for &a in &ans { *map.entry(a).or_insert(0) += 1; } let mut ret = vec![]; for (&k,&v) in map.iter() { ret.push((k,v)); } ret } } fn main() { input! { (n,k): (i64,i64), } let p = SieveOfEratosthenes::new(2000000); let mut val = n; let mut map = HashMap::new(); for &p in &p.primes { let x = p as i64; while val%x==0 { val /= x; *map.entry(x).or_insert(0) += 1; } } let mut ans = M::new(1); for (_,&v) in map.iter() { let mut tmp = M::new(1); for i in 0..v { tmp *= M::from((k+v-i)%MOD); tmp *= M::from(i+1).inv(); } ans *= tmp; } println!("{}",ans); }