Merging Sequences#5196
Sign in

Merging Sequences

1 second
64 megabytes
Medium

Given two infinite non-decreasing sequences and . Find the -th element in the non-decreasing sequence , which contains all elements from and (including duplicates).

The sequence is defined using the polynomial P(x) = x^3 as follows:

a_1 = P(1) \bmod 12345,\quad a_i = a_{i-1} + (P(i) \bmod 12345),\quad \text{for } i > 1

The sequence is defined using the polynomial Q(x) = x^2 as follows:

b_1 = Q(1) \bmod 123,\quad b_i = b_{i-1} + (Q(i) \bmod 123),\quad \text{for } i > 1

Input

The input file contains the integer (1 \leq k \leq 10^7).

Output

Output one integer—the answer to the problem. It is guaranteed that the answer does not exceed 2 \cdot 10^9.

Examples

Example 1

Loading
Loading