При підготовці до олімпіади з інформатики Петрик П’яточкін вирішив не полишати задач про подільність чисел. Хто його зна, а раптом така чи подібна задача трапиться цього року? Для заданного натурального числа N встановити кількість та суму всіх можливих взаємно різних остач від ділення на такі числа: 1, 2, 3, ..., N-2, N-1, N. Вимоги до програми: Програма повинна зчитувати вхідні дані із консолі. В першому рядку міститься одне ціле число N (1 ≤ N ≤ 1 000 000 000). Результат виконання програми повинен записуватися у консоль. У першому рядку виводиться два цілих числа, що відокремлені пропуском: кількість усіх можливих взаємно різних остач від ділення на вказані в умові числа, а також сума таких остач від ділення, яка обчислена за модулем 123456789 (остача від ділення отриманої суми на число 123456789).