Не дуже потужний

Вхідні дані

Перший рядок містить єдине ціле число $t$ ( $1 \leq t \leq 1 0^{5}$ 1 \le t \le 10^5) $-$ кількість тестових випадків.

Перший рядок кожного тестового випадку містить єдине ціле число $n$ ( $1 \leq n \leq 5 \cdot 1 0^{5}$ 1 \le n \le 5 \cdot 10^5) $-$ розмір масиву.

Другий рядок кожного тестового випадку містить $n$ цілих чисел $a_{i}$ a_i ( $0 \leq a_{i} \leq 1 0^{9}$ 0 \le a_i \le 10^9) $-$ елементи масиву.

Гарантується, що сума $n$ по всіх тестових випадках не перевищує $5 \cdot 1 0^{5}$ 5 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть єдине ціле число — $f (a)$ .

Приклади

Приклад 1

Loading

Примітка

У першому тестовому випадку підпослідовностями є $[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]$ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3].

$v ([]) = 0$ v([]) = 0.

$v ([1]) = (- 1)^{1} = - 1$ v([1]) = (-1)^1 = -1 , $v ([2]) = (- 2)^{1} = - 2$ v([2]) = (-2)^1 = -2 , $v ([3]) = (- 3)^{1} = - 3$ v([3]) = (-3)^1 = -3.

$v ([1, 2]) = (- 1)^{1} + (- 2)^{2} = - 1 + 4 = 3$ v([1,2]) = (-1)^1 + (-2)^2 = -1+4 = 3.

$v ([1, 3]) = (- 1)^{1} + (- 3)^{2} = - 1 + 9 = 8$ v([1,3]) = (-1)^1 + (-3)^2 = -1+9 = 8.

$v ([2, 3]) = (- 2)^{1} + (- 3)^{2} = - 2 + 9 = 7$ v([2,3]) = (-2)^1 + (-3)^2 = -2+9 = 7.

$v ([1, 2, 3]) = (- 1)^{1} + (- 2)^{2} + (- 3)^{3} = - 1 + 4 - 27 = - 24$ v([1,2,3]) = (-1)^1 + (-2)^2 + (-3)^3 = -1 + 4 - 27 = -24.

Отже, $f (a) = 0 - 1 - 2 - 3 + 3 + 8 + 7 - 24 = - 12$ f(a) = 0-1-2-3+3+8+7-24 = -12.

$- 12$ mod $1000000007$ = $999999995$ .

Оцінювання

Підзадача $1$ ( $300$ балів): Без додаткових обмежень.