Determinant of a Möbius Inversion Matrix

We are given three positive integers (n), (s), and (t). Construct an (n\times n) matrix (A) whose (i,j)-th element is defined as [ a_{i,j} = \sum_{d \mid \gcd(i,j)} \mu\Bigl(\frac{\gcd(i,j)}{d}\Bigr)\bigl(\sigma_0(d^s)\bigr)^t, \quad 1 \le i,j \le n, ] where (\mu) is the Möbius function and (\sigma_0) denotes the divisor counting function. Recall that for any positive integer (x) with prime factorization (x = p_1^{a_1}\cdots p_k^{a_k}), we have (\sigma_0(x)=a_1+1) when (x) is a prime power. In particular, since (d^s) is a perfect power, if (d=p^a) then (\sigma_0(d^s)=a,s+1).

A classical result (the Smith determinant) shows that for a matrix defined by (A_{ij} = F(\gcd(i,j))) one has [ \det A = \prod_{i=1}^{n} (F\ast\mu)(i), ] where ((F \ast \mu)(n)=\sum_{d\mid n}\mu\Bigl(\frac{n}{d}\Bigr)F(d)). Here, setting (F(d)=(\sigma_0(d^s))^t), we deduce that [ \det A = \prod_{i=1}^{n} g(i)\quad\text{with}\quad g(i)=\sum_{d\mid i}\mu\Bigl(\frac{i}{d}\Bigr)(\sigma_0(d^s))^t. ]

Since both (\mu(\cdot)) and (\sigma_0(\cdot)) are multiplicative functions, one may show that for a prime power (p^a) (with (a\ge1)) the function (g) satisfies [ g(p^a) = ((a,s+1)^t - (((a-1),s+1)^t). ] For (a=0) (i.e. for (n=1)), we have (g(1)=1).

Your task is to compute (\det A \bmod (10^9+7)).

inputFormat

The input consists of a single line containing three space‐separated integers (n), (s), and (t) (with (n \ge 1) and (s, t \ge 1)).

outputFormat

Output a single integer: the value of (\det A \bmod (10^9+7)).

sample

1 1 1

1