Для заданої квадратної матриці розмірності ~N \times N~ знайти модуль різниці сум діагональних елементів.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~ (~1 \le N \le 10^3~)

Наступні ~N~ рядків містять по ~N~ цілих чисел від -100 до 100.

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести модуль різниці сум діагональних елементів.

Примітка

До прикладу 1:

Сума елементів першої діагоналі: 1+5+9=15.

Сума елементів другої діагоналі: 3+5+9+17.

|15-17| = 2.

Приклад вхідних даних

3
1 2 3
4 5 6
9 8 9

Приклад вихідних даних

2

Задаються три цілих числа ~a_1~, ~a_2~, ~a_3~ - перші члени арифметичної або геометричної прогресії.

Визначити, до якої з двох прогресій належать ці числа та знайти наступний член цієї послідовності.

Формат вхідних даних

Вхідний потік містить цілі числа ~a_1~, ~a_2~, ~a_3~ (~-10000 \le a_1,a_2,a_3 \le 10000~).

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести в єдиному рядку повідомлення ~AP~ у випадку арифметичної прогресії або ~GP~, у випадку геометричної прогресії. Через пропуск вивести наступний член прогресії.

Приклад вхідних даних

4 7 10

Приклад вихідних даних

AP 13

Приклад вхідних даних

2 6 18

Приклад вихідних даних

GP 54

Для цілого числа ~n~ (~n \geq 0~) визначимо ~f(n)~ так:

• ~f(n) = 1~(якщо ~n < 2~)

• ~f(n) = n \times f(n-2)~ (якщо ~n \geq 2~)

Дано ціле число ~N~.

Знайдіть кількість кінцевих нулів у десятковому записі ~f(N)~.

Формат вхідних даних

Вхідний потік містить ціле число ~N~ (~0 \le N \le 10^{18}~).

Формат вихідних даних

У вихідний потік вивести шукану кількість нулів.

Примітка

До прикладу 1:

f(12)=12×10×8×6×4×2=46080, що має один кінцевий нуль.

Приклад вхідних даних

12

Приклад вихідних даних

1

Приклад вхідних даних

5

Приклад вихідних даних

0

Приклад вхідних даних

1000000000000000000

Приклад вихідних даних

124999999999999995

Маємо послідовність цілих чисел ~A~ довжини ~N~, де ~A_1 = X~, ~A_{i+1} = A_i+D~ (~1 \leq i < N~).

Степан візьме деякі (можливо всі або жодного) з елементів у цій послідовності, а Андрій візьме всі інші.

Нехай ~S~ і ~T~ --- сума чисел, узятих Степаном та Андрієм відповідно.

Скільки існує можливих значень ~S - T~?

Формат вхідних даних

Вхідний потік містить цілі числа ~N, X, D~ (~1 \le N \le 2 \times 10^5~, ~-10^8 \le X,D \le 10^8~).

Числа у рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шукану кількість.

Примітка

До прикладу 1:

А є (4, 6, 8). Є вісім способів взяти елементи:

((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8) ), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4 ))) і ((4, 6, 8 ), ()).

Значення ~S - T~ у цих способах становлять -18, -10, -6, -2, 2, 6, 10 і 18, відповідно, тому існує вісім можливих значень ~S - T~.

Приклад вхідних даних

3 4 2

Приклад вихідних даних

8

Приклад вхідних даних

2 3 -3

Приклад вихідних даних

2

Приклад вхідних даних

100 14 20

Приклад вихідних даних

49805

Для двох послідовностей ~S~ і ~T~ довжини ~N~, що складаються з 0 і 1, визначимо ~f(S, T)~ таким чином:

• Розглянемо повторення наступної операції над ~S~ так, щоб ~S~ дорівнювала ~T~. ~f(S, T)~ --- мінімально можлива загальна вартість цих операцій.

  ---Змінити ~S_i~(з 0 на 1 або навпаки). Вартість цієї операції дорівнює ~D \times C_i~, де ~D~ --- кількість цілих чисел ~j~, таких що ~S_j \neq T_j~ (~1 \leq j \leq N~) безпосередньо перед цією зміною.

Існує ~2^N \times (2^N - 1)~ пар (~S, T~) різних послідовностей довжини ~N~, що складаються з 0 і 1.

Обчисліть суму ~f(S, T)~ над усіма цими парами за модулем (~10^9 + 7~).

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~ (~1 \le N \le 2 \times 10^5~)

Наступний рядок містить ~N~ цілих чисел ~C_i~ (~1 \le C_i \le 10^9~).

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шукану суму.

Примітка

До прикладу 1:

Існують дві пари (~S, T~) різних послідовностей довжиною 2, які складаються з 0 і 1, а саме:

• ~S = (0), T = (1)~: змінюючи ~S_1~ на 1, ми можемо отримати ~S = T~ за ціною 1000000000, отже, ~f(S, T) = 1000000000~.

• ~S = (1), T = (0)~: змінюючи ~S_1~ на 0, ми можемо отримати ~S = T~ за ціною 1000000000, тому ~f(S , T) = 1000000000~.

Сума їх дорівнює 2000000000, і ми повинні вивести її за модулем (~10^9 + 7~), тобто 999999993.

Приклад вхідних даних

1
1000000000

Приклад вихідних даних

999999993

Приклад вхідних даних

2
5 8

Приклад вихідних даних

124

Приклад вхідних даних

5
52 67 72 25 79

Приклад вихідних даних

269312