Jumping Divisor Qualifier

In this problem, we say that a fertilizer with an initial depth (d) (in meters) qualifies if there exists a sequence of jumps that brings it to a depth of (1). The jumping process is defined as follows:

1. At a current depth (d > 1), compute all of its proper divisors (i.e. all positive divisors strictly less than (d)).

2. A jump consists of choosing one of these proper divisors (each jump length may be used at most once during the process) and subtracting it from the current depth, resulting in a new depth (d - x), where (x) is the chosen proper divisor.

3. The process continues as long as there is at least one valid jump (i.e. a proper divisor that has not been used before) from the current depth. If at some point no jump is possible and the depth is not (1), the process fails.

A fertilizer is considered qualified if there exists at least one sequence of valid jumps ending with a depth of (1).

It turns out that the only numbers that are qualified are exactly the powers of (2). For example, consider (d = 16):

• The proper divisors of (16) are (8, 4, 2, 1). By choosing (8) we reach (16-8=8).
• Then from (8) (whose proper divisors are (4,2,1)) choose (4) to get (8-4 = 4).
• From (4) (with proper divisors (2,1)) choose (2) to get (4-2 = 2).
• Finally, for (2) (with sole proper divisor (1)) choose (1) to reach (2-1 = 1).

Thus, the sequence (16 \to 8 \to 4 \to 2 \to 1) works, and similarly every power of (2) has a valid jump sequence.

Given that the qualified fertilizers are precisely the numbers of the form (2^n) (with (n \ge 1)), if we list all qualified fertilizers in increasing order we get: (2, 4, 8, 16, \dots). Your task is:

Given an integer (k), output the initial depth of the (k)-th qualified fertilizer (i.e. the (k)-th power of (2)) modulo (123456789). That is, compute (2^k \bmod 123456789).

inputFormat

The input consists of a single line containing one integer (k) ((1 \le k \le 10^{9}) or as specified by the problem constraints).

outputFormat

Output a single integer, the (k)-th power of (2) modulo (123456789).

sample

1

2