Cho một mảng $A$ có độ dài $N$, bạn cần chia mảng thành hai tập con $R_1$ và $R_2$ (có thể rỗng), sao cho:

• Tổng tất cả các phần tử trong $R_1$ là số chẵn
• Tổng tất cả các phần tử trong $R_2$ là số chẵn

Hãy đếm số phương án thỏa mãn, lấy dư cho $10^9+7$.

Dữ liệu vào

Dòng đầu tiên là một số nguyên $T$, biểu thị số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu tiên là một số nguyên $N$, biểu thị độ dài mảng.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên, là số phương án lấy dư cho $10^9+7$.

Ví dụ

Input

2
3
2 4 6
3
1 3 5

Output

4
0

Ghi chú

Giải thích ví dụ

Bộ dữ liệu thứ nhất: có 4 phương án để tổng của $R_1$ và tổng của $R_2$ đều là số chẵn.

Bộ dữ liệu thứ hai: không thể thỏa mãn điều kiện, in ra 0.

Phạm vi dữ liệu

• $1 \le T \le 10$
• $1 \le N \le 1000$
• $1 \le A_i \le 10^9$