Verifying the GCD–LCM Product

Given a positive integer N, compute the following product modulo (104857601):

[ P = \prod_{i=1}^N \prod_{j=1}^N \frac{\mathrm{lcm}(i,j)}{\mathrm{gcd}(i,j)} \pmod{104857601}. ]

Using the identity (\mathrm{lcm}(i,j) \times \mathrm{gcd}(i,j) = i \times j), we have

[ \frac{\mathrm{lcm}(i,j)}{\mathrm{gcd}(i,j)} = \frac{i \times j}{\mathrm{gcd}(i,j)^2}. ]

Thus the product can be rewritten as

[ P = \prod_{i=1}^N \prod_{j=1}^N \frac{i \times j}{\mathrm{gcd}(i,j)^2} \pmod{104857601}. ]

A neat way to solve this problem is to work with the exponents of primes. For any prime (p), note that

[ \sum_{i=1}^N v_p(i) = \sum_{k \ge 1} \left\lfloor \frac{N}{p^k} \right\rfloor, ]

and also

[ \sum_{i=1}^N \sum_{j=1}^N v_p(\mathrm{gcd}(i,j)) = \sum_{k \ge 1} \left\lfloor \frac{N}{p^k} \right\rfloor^2. ]

Hence the exponent of (p) in (P) is given by

[ E_p = 2N \left( \sum_{k \ge 1} \left\lfloor \frac{N}{p^k} \right\rfloor \right) - 2\left( \sum_{k \ge 1} \left\lfloor \frac{N}{p^k} \right\rfloor^2 \right). ]

Then the final answer is

[ P \equiv \prod_{p \le N} p^{E_p} \pmod{104857601}. ]

It is guaranteed that the answer computed using the above method will pass all test cases. Note that earlier strict time constraints have been relaxed.

inputFormat

The input consists of a single line containing one integer (N) ((1 \le N \le \text{some upper bound})).

outputFormat

Output a single integer, the value of (P) modulo (104857601).

sample

1

1