Kölgə massivi

Giriş

Birinci sətirdə bir tam ədəd $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test hallarının sayı verilir.

Hər test halının birinci sətrində bir tam ədəd $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \le n \le 10^6) — massivin uzunluğu verilir.

Hər test halının ikinci sətrində $n$ tam ədəd $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) — kölgə massivi $h$ -in elementləri verilir.

$n$ qiymətlərinin bütün test halları üzrə cəminin $1 0^{6}$ 10^6-dan çox olmadığı təmin edilir.

Çıxış

Hər test halı üçün bir tam ədəd — düzgün ilkin $a$ massivlərinin sayını $1 0^{9} + 7$ 10^9 + 7 moduluna görə çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halında $h = [2, 2, 2]$ h = [2, 2, 2]. Bu kölgə massivini yaradan dəqiq $2$ düzgün ilkin $a$ massivi var:

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

Bal hesablama

Altməsələ $1$ ( $40$ bal): $\sum n \leq 8$ \sum n \le 8 və $h_{i} \leq 8$ h_i \le 8.
Altməsələ $2$ ( $160$ bal): $\sum n \leq 1000$ \sum n \le 1000 və $h_{i} \leq 100$ h_i \le 100.
Altməsələ $3$ ( $200$ bal): Əlavə məhdudiyyət yoxdur.