---

Problem 682

---

$5$-Smooth Pairs

$5$-smooth numbers are numbers whose largest prime factor doesn’t exceed $5$.
$5$-smooth numbers are also called Hamming numbers.

Let $\mathrm{\Omega }(a)$ be the count of prime factors of $a$ (counted with multiplicity).
Let $s(a)$ be the sum of the prime factors of $a$ (with multiplicity).
For example, $\mathrm{\Omega }(300)=5$ and $s(300)=2+2+3+5+5=17$.

Let $f(n)$ be the number of pairs, $(p,q)$, of Hamming numbers such that $\mathrm{\Omega }(p)=\mathrm{\Omega }(q)$ and $s(p)+s(q)=n$.
You are given $f(10)=4$ (the pairs are $(4,9),(5,5),(6,6),(9,4)$) and $f({10}^2)=3629$.

Find $f({10}^7)mod1000000007$.

---

$5$-光滑数对

$5$-光滑数是指最大质因数不超过$5$的数。
$5$-光滑数也被称为汉明数。

记$\mathrm{\Omega }(a)$为$a$的质因数数目（包括重复的质因数）。
记$s(a)$为$a$的质因数之和（包括重复的质因数）。
例如，$\mathrm{\Omega }(300)=5$，$s(300)=2+2+3+5+5=17$。

记$f(n)$为所有满足$\mathrm{\Omega }(p)=\mathrm{\Omega }(q)$和$s(p)+s(q)=n$的汉明数对$(p,q)$的数目。
已知$f(10)=4$（包括$(4,9),(5,5),(6,6),(9,4)$），$f({10}^2)=3629$。

求$f({10}^7)mod1000000007$。

---