Слияние последовательностей

Даны две бесконечные неубывающие последовательности A и B. Требуется найти k-ый элемент в неубывающей последовательности C, содержащей все элементы из A и B (включая повторы).

Последовательность A задается с помощью полинома P(x) = x^3:

a_1 = P(1) mod 12345, a_i = a_{i-1} + (P(i) mod 12345), при i > 1

Последовательность B задается с помощью полинома Q(x) = x^2:

b_1 = Q(1) mod 123, b_i = b_{i-1} + (Q(i) mod 123), при i > 1

Входные данные

Входной файл содержит натуральное число k (1 ≤ k ≤ 10^7).

Выходные данные

В выходной файл выведите одно число - ответ на задачу. Гарантируется, что ответ не превышает 2·10^9.

Примеры