Миша любит экспериментировать с числами. На этот раз у Миши есть массив четной длины из $$$n$$$ элементов, и он хочет сократить количество элементов до двух.
Для этого Миша сначала заменяет все элементы $$$a_i$$$ на $$$a_i = a_i + a_{i + 2}$$$ для всех $$$i$$$ от 1 до $$$n - 2$$$ включительно, а затем удаляет два последних элемента в массиве. И делает это до тех пор, пока у него не останется только два числа.
Вы хотите узнать, какие два числа останутся у Миши. Так как числа могут получиться слишком большими, то выведите их остаток от деления на число $$$10^9 + 7$$$.
В первой строке задано чётное число $$$n$$$ — размер массива $$$(2 \leq n \leq 2 \cdot 10^5)$$$.
В следующей строке заданы $$$n$$$ целых чисел $$$a_i$$$ — элементы массива $$$(1 \leq a_i \leq 10^9)$$$.
Выведите два числа — оставшиеся элементы массива по модулю $$$10^9 + 7$$$.
| Группа | Баллы | Доп. ограничения | Система оценки |
| $$$0$$$ | $$$0$$$ | — | Тесты из условия |
| $$$1$$$ | $$$20$$$ | $$$n \leq 10, a_i \leq 100$$$ | Полная группа |
| $$$2$$$ | $$$12$$$ | $$$n \leq 10^4$$$ | Полная группа |
| $$$3$$$ | $$$23$$$ | $$$a_i = 1$$$ | Полная группа |
| $$$4$$$ | $$$45$$$ | — | Полная группа |
61 2 3 4 5 6
12 16
Итерации в примере:
[1, 2, 3, 4, 5, 6]
[4, 6, 8, 10]
[12, 16]
