Ominsik Number

You are given a positive integer N. Find the smallest positive integer that is divisible by every integer from 1 through N.

Because this value can be very large, output only its remainder when divided by 987654321.

The first line contains a positive integer N. N is between 1 and 1,000,000 inclusive.

Print the remainder when the smallest positive integer divisible by every integer from 1 through N is divided by 987654321.