Problems
Слияние последовательностей
Слияние последовательностей
Даны две бесконечные неубывающие последовательности \textbf{A} и \textbf{B}. Требуется найти \textbf{k}-ый элемент в неубывающей последовательности \textbf{C}, содержащей все элементы из \textbf{A} и \textbf{B} (включая повторы).
Последовательность \textbf{A} задается с помощью полинома \textbf{P(x) = x^3}:
\textbf{a_1 = P(1) mod 12345, a_i = a_\{i-1\} + (P(i) mod 12345)}, при \textbf{ i > 1}
Последовательность \textbf{B} задается с помощью полинома \textbf{Q(x) = x^2}:
\textbf{b_1 = Q(1) mod 123, b_i = b_\{i-1\} + (Q(i) mod 123)}, при\textbf{ i > 1}
\InputFile
Входной файл содержит натуральное число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^7}).
\OutputFile
В выходной файл выведите одно число - ответ на задачу. Гарантируется, что ответ не превышает \textbf{2·10^9}.
Input example #1
1
Output example #1
1