Problem 636

Restricted Factorisations

Consider writing a natural number as product of powers of natural numbers with given exponents, additionally requiring different base numbers for each power.

For example, $256$ can be written as a product of a square and a fourth power in three ways such that the base numbers are different.
That is, $256 = 1^{2} \times 4^{4} = 4^{2} \times 2^{4} = 16^{2} \times 1^{4}$ .

Though $4^{2}$ and $2^{4}$ are both equal, we are concerned only about the base numbers in this problem. Note that permutations are not considered distinct, for example $16^{2} \times 1^{4}$ and $1^{4} \times 16^{2}$ are considered to be the same.

Similarly, $10!$ can be written as a product of one natural number, two squares and three cubes in two ways ( $10! = 42 \times 5^{2} \times 4^{2} \times 3^{3} \times 2^{3} \times 1^{3} = 21 \times 5^{2} \times 2^{2} \times 4^{3} \times 3^{3} \times 1^{3}$ ) whereas $20!$ can be given the same representation in $41680$ ways.

Let $F (n)$ denote the number of ways in which $n$ can be written as a product of one natural number, two squares, three cubes and four fourth powers.

You are given that $F (25!) = 4933$ ,
$F (100!) \mod 1 000 000 007 = 693 952 493$ ,
and $F (1 000!) \mod 1 000 000 007 = 6 364 496$ .

Find $F (1 000 000!) \mod 1 000 000 007$ .

有限制的因数分解

考虑将自然数表示成一系列给定指数的幂的乘积，同时要求这些幂的底数互不相同。

例如，将 $256$ 表示成一个平方数乘以一个四次方数，且底数互不相同，有三种不同的方式，分别是
$256 = 1^{2} \times 4^{4} = 4^{2} \times 2^{4} = 16^{2} \times 1^{4}$ 。

尽管 $4^{2}$ 和 $2^{4}$ 是相等的，但是在这个问题中我们只要求底数不同。还要注意，改变排列方式并不认为是不同的表示方式，例如 $16^{2} \times 1^{4}$ 和 $1^{4} \times 16^{2}$ 是相同的表示。

类似地，将 $10!$ 表示成一个自然数、两个平方数和三个立方数的乘积，有两种方式（ $10! = 42 \times 5^{2} \times 4^{2} \times 3^{3} \times 2^{3} \times 1^{3} = 21 \times 5^{2} \times 2^{2} \times 4^{3} \times 3^{3} \times 1^{3}$ ），而 $20!$ 则有 $41680$ 种表示方式。

记 $F (n)$ 为将 $n$ 表示成一个自然数、两个平方数、三个立方数和四个四次方数的方式总数。

已知 $F (25!) = 4933$ ，
$F (100!) \mod 1 000 000 007 = 693 952 493$ ，
$F (1 000!) \mod 1 000 000 007 = 6 364 496$ 。

求 $F (1 000 000!) \mod 1 000 000 007$ 。