Cütlərin Sayılması

Giriş

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

İkinci sətir tək bir tam ədəd $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — $a$ massivinin uzunluğu.

Üçüncü sətir $n$ ayrılmış tam ədəd $a_{1}, a_{2}, .., a_{n}$ a_1,a_2,..,a_n $(1 \leq a_{1}, a_{2}, a_{3}, ..., a_{n} \leq 1 0^{9})$ (1 \le a_1,a_2,a_3,...,a_n \le 10^9) — $a$ massivi.

Ümumi test hallarının $\sum n \leq 1 0^{6}$ \sum n \le 10^6 olması təmin edilir.

Çıxış

Hər test halı üçün tək bir tam ədəd — tələb olunan çıxış cavabını 1e6+3-ə modulu cütlərin sayı

Nümunələr

Nümunə 1

Loading

Bal hesablama

Subtapşırıq $1$ ( $10$ bal) : $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000) və $(1 \leq a_{i} \leq 9)$ (1 \le a_i \le 9)
Subtapşırıq $2$ ( $40$ bal) : $(1 \leq a_{i} \leq 4)$ (1 \le a_i \le 4)
Subtapşırıq $3$ ( $50$ bal) : Əlavə məhdudiyyət yoxdur