Background

Originally created by @rainheavy.

This is a very (du) easy (liu) problem.

The 1st China International Import Expo was held in Shanghai from 2018.11.5 to 2018.11.10. The country ruled by Trump, the “beautiful country” (Meiliguo, pinyin), brought Jinkela. This is a magical product. According to their advertisements: if you use Jinkela fertilizer, it can absorb nitrogen, phosphorus, and potassium from depths below 20 meters.

However, when it was inspected by the quality inspector DevZhu from “Futukang” (pinyin), some problems were found. The effect of Jinkela was not as the advertisement said. After all, plant roots can only reach depth $1$, so the effect of Jinkela is limited.

Problem Description

It only has the following effect (take $20$ as an example).

The proper divisors of $20$ are $10, 5, 4, 2, 1$.

From a depth of $20$ meters underground, you can jump upward by a length equal to one divisor. (For example, $10$.)

Now it is at depth $10$ meters. The proper divisors of $10$ are $5, 2, 1$.

Jump another $5$ to reach $5$. The proper divisors of $5$ are $1$.

Jump $1$ to reach $4$. The proper divisors of $4$ are $2, 1$.

$1$ has already been used, so it cannot be used again.

Jump another $2$ to reach $2$. The proper divisors of $2$ are $1$.

$1$ has already been used, so it cannot jump anymore. The final depth is $2$.

Following the rules above, try all possible jump sequences that are allowed. If there exists at least one sequence whose final result is $1$, then this fertilizer is qualified; otherwise it is not qualified.

DevZhu is facing a large pile of Jinkela to be tested and does not want to test so many. He wants to ask which Jinkela are qualified, and among these qualified ones, which one is the $k$-th by initial depth.

Sort the qualified Jinkela by initial depth from small to large. Output the initial depth of the $k$-th qualified Jinkela modulo $123456789$. (Futukang never uses $10^9+7$ or $998244353$.)

Input Format

One number $k$.

Output Format

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

1

1

2

2

Hint

(It is super easy...)

(A little benefit for those who cannot do it: there is one testdata with $k = 1$.)

Constraints:

For $30\%$ of the testdata, $k \le 10^5$.

For $70\%$ of the testdata, $k \le 10^9$.

For $100\%$ of the testdata, $k \le 10^{18}$.

Translated by ChatGPT 5