| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 21 | 18 | 17 | 94.444% |
The Pokémon Conservation Society protects Pokémon and their habitats all around the globe. In recent research, data about $h$ habitats was collected.
Each habitat may be inhabited by several Pokémon species. Researchers know how many limbs each species has. Pokémon are swift and extremely good at hiding, so researchers were only able to detect the total number of limbs in each of the habitats.
Researchers understand that it might not be possible to find the population of each species, but would like to understand how much uncertainty is left. How many different combinations of Pokémon would have the observed number of limbs?
The first line contains a single integer $h$ (1ドル \le h \le 1,024円$) --- the number of habitats. The next $h$ lines contain the description of each habitat.
Each line starts with two integers $t$ and $s$ (0ドル \le t \le 10^9,ドル 1ドル \le s \le 3$), where $t$ is the total number of limbs, and $s$ is the number of species in the habitat. They are followed by $s$ integers $l_i$ (1ドル \le l_i \le 16$) --- the number of limbs for each species.
Output the number of possible combinations of Pokémon in each habitat. Output should contain $h$ lines with a single integer.
3 6 1 3 6 2 2 3 6 3 1 2 3
1 2 7
4 1000000000 3 1 1 1 0 3 2 4 5 17 2 2 4 34 3 5 3 2
500000001500000001 1 0 25