Ardıcılıqların birləşməsi

Verilmiş iki sonsuz artan sıra A və B var. Bu sıralar (təkrarlar daxil olmaqla) bütün elementləri ehtiva edən artan sıra C-də k-cı elementi tapmaq lazımdır.

A sırası P(x) = x^3 polinomu ilə müəyyən edilir:

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

B sırası Q(x) = x^2 polinomu ilə müəyyən edilir:

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

Giriş verilənləri

Giriş faylı təbii ədəd k (1 ≤ k ≤ 10^7) ehtiva edir.

Çıxış verilənləri

Çıxış faylına məsələnin cavabını - bir ədəd yazın. Cavabın 2·10^9-dan çox olmayacağı təmin edilir.

Nümunələr