Minimum Tile Purchase Product

To fully unlock the magic of the "Wanbao Hammer", Xiaowan needs to cover a square floor (with a fixed pattern) using only one type of rectangular tile of fixed dimensions a × b without rotating or overlapping them. To achieve the best resonance, the floor must be completely covered by a square of arbitrary side length.

In each purchase, Xiaowan can only buy tiles of a given size a × b. In order to save money, she will buy the minimum number of such tiles so that they can be arranged to exactly cover a square.

It can be shown that the minimum number of tiles required when tiling a square with side length L is achieved by taking L = \mathrm{lcm}(a, b). Since \(\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}\), the minimum number of tiles needed is:

[ \frac{\mathrm{lcm}(a,b)^2}{a\times b} = \frac{\Big(\frac{a\times b}{\gcd(a,b)}\Big)^2}{a\times b} = \frac{a\times b}{\gcd(a,b)^2}. ]

Your task is: given a positive integer n, for each pair \((a,b)\) with \(1 \le a, b \le n\), compute \(f(a,b)=\frac{a\times b}{\gcd(a,b)^2}\) and output the product of all such values modulo 19260817.

inputFormat

The input consists of a single integer n (\(1 \le n \le N\)), where N is subject to problem constraints. It represents that you need to consider every pair \((a,b)\) with \(1 \le a, b \le n\).

outputFormat

Output a single integer, the product of \(f(a, b)=\frac{a\times b}{\gcd(a,b)^2}\) for all pairs \((a, b)\) where \(1 \le a,b \le n\), taken modulo 19260817.

sample

1

1