Background

@rainheavy original

This is an extremely (du) simple (liu) problem.

The first China International Expo was held in Shanghai from November 5th to November 10th, 2018. The country under Trump's rule, the United States, brought Jinkela. This is a magical product, using Jinkela as fertilizer allows absorption of nitrogen, phosphorus, and potassium from 20 meters below (this is their advertisement).

However, during the quality inspection by the quality inspector DevZhu at Futu (tu) Kang, a problem was discovered. The effect of Jinkela is not as advertised. After all, the roots of plants can only reach a depth of 1 meter, and the effect of Jinkela is limited.

Problem Description

Its effect can only be as follows: (taking 20 as an example)

The divisors of 20 (excluding itself) are 10, 5, 4, 2, 1.

From 20 meters underground, it can jump up by the length of a divisor (such as 10).

Now it is at 10 meters, the divisors of 10 (excluding itself) are 5, 2, 1.

Jump by 5, to 5 meters, the divisors of 5 (excluding itself) are 1.

Jump by 1, to 4 meters, the divisors of 4 (excluding itself) are 2, 1.

1 has already been used and cannot be used again.

Jump by 2, to 2 meters. The divisors of 2 (excluding itself) are 1.

1 has already been used.
At this point, it cannot jump anymore. The current depth is 2.

According to the above requirements, try all possible jumps. As long as there is one situation where the final result is 1, the fertilizer is qualified; otherwise, it is unqualified.

DevZhu faces a pile of Jinkela to be inspected and does not want to inspect so many. He wants to ask you which Jinkela are qualified. Among the qualified Jinkela, which one is the k-th in terms of initial depth?

Sort the qualified Jinkela by initial depth in ascending order, and output the initial depth of the k-th Jinkela modulo $123456789$ (Futu Kang never uses $1e9+7$ and $998244353$).

Input Format

A number $k$.

Output Format

The initial depth of the k-th qualified Jinkela modulo $123456789$.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

2

Notes

(This is so simple...)

(A little benefit for those who don't know: there is one data point that is 1.)

For 30% of the data, $k$ <= $10^5$;

For 70% of the data, $k$ <= $10^9$;

For 100% of the data, $k$ <= $10^{18}$.

见题面 Input 部分

见题面 Output 部分