P402857 - GYM100923 A Por Costel and Azerah - SSOJ

Memory Limit：64 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

A. Por Costel and Azerahtime limit per test2 secondsmemory limit per test64 megabytesinputazerah.inoutputazerah.out $\text{[math]}$

Por Costel the Pig has received a royal invitation to the palace of the Egg-Emperor of Programming, Azerah. Azerah had heard of the renowned pig and wanted to see him with his own eyes. Por Costel, having arrived at the palace, tells the Egg-Emperor that he looks "tasty". Azerah feels insulted (even though Por Costel meant it as a compliment) and, infuratied all the way to his yolk, threatens to kill our round friend if he doesn't get the answer to a counting problem that he's been struggling with for a while

Given an array of numbers, how many non-empty subsequences of this array have the sum of their numbers even ? Calculate this value mod $\text{[math]}$ (Azerah won't tell the difference anyway)

Help Por Costel get out of this mischief!

Input

The file azerah.in will contain on its first line an integer $\text{[math]}$ , the number of test cases. Each test has the following format: the first line contains an integer $\text{[math]}$ (the size of the array) and the second line will contain $\text{[math]}$ integers $\text{[math]}$ ( $\text{[math]}$ ), separated by single spaces.

It is guaranteed that the sum of $\text{[math]}$ over all test cases is at most $\text{[math]}$

Output

The file azerah.out should contain $\text{[math]}$ lines. The $\text{[math]}$ -th line should contain a single integer, the answer to the $\text{[math]}$ -th test case.

ExampleInput

Output

3
3

2015 ACM National Contest Romania - Round 1

402857: GYM100923 A Por Costel and Azerah

Description

Source/Category

加入题单