Ominsik Number

Time limit2sMemory limit128 MB

Summary
Given N up to one million, compute the least common multiple of all integers from 1 to N modulo 987654321.
Level

Medium5 of 10

Topics
Number theory, Math, Implementation
Solved
No attempts yet

Problem

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.

Input

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

Output

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

Examples5

  1. Example 1

    Input
    10
    Expected output
    2520

  2. Example 2

    Input
    1
    Expected output
    1

  3. Example 3

    Input
    3
    Expected output
    6

  4. Example 4

    Input
    1234
    Expected output
    411860547

  5. Example 5

    Input
    97969
    Expected output
    528039414