Тіньовий масив

Вхідні дані

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

Перший рядок кожного набору вхідних даних містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \le n \le 10^6) — довжину масиву.

Другий рядок кожного набору вхідних даних містить $n$ цілих чисел $h_{1}, h_{2}, \dots, h_{n}$ h_1, h_2, \dots, h_n ( $1 \leq h_{i} \leq 1 0^{9}$ 1 \le h_i \le 10^9) — елементи тіньового масиву $h$ .

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

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число — кількість допустимих початкових масивів $a$ за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Loading

Примітка

У першому наборі вхідних даних $h = [2, 2, 2]$ h = [2, 2, 2]. Існує рівно $2$ допустимі початкові масиви $a$ , які породжують цей тіньовий масив:

$a = [2, 1, 2]$ a = [2, 1, 2]
$a = [2, 2, 2]$ a = [2, 2, 2]

Оцінювання

Підзадача $1$ ( $40$ балів): $\sum n \leq 8$ \sum n \le 8 і $h_{i} \leq 8$ h_i \le 8.
Підзадача $2$ ( $160$ балів): $\sum n \leq 1000$ \sum n \le 1000 і $h_{i} \leq 100$ h_i \le 100.
Підзадача $3$ ( $200$ балів): Без додаткових обмежень.