Joy of Pokémon Observation

시간 제한3초메모리 제한2048 MB

요약

각 서식지에서 주어진 종들의 개체 수 조합 중 다리 수 합이 정확히 t가 되는 경우의 수를 센다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
3
6 1 3
6 2 2 3
6 3 1 2 3
```
예상 출력
```
1
2
7
```

예제 2

입력

4
1000000000 3 1 1 1
0 3 2 4 5
17 2 2 4
34 3 5 3 2

예상 출력

500000001500000001
1
0
25