포켓몬 관측의 즐거움

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

요약

각 서식지의 총 다리 수 t와 종별 다리 수 l_i(종은 최대 3개)가 주어질 때, sum l_i x_i = t를 만족하는 음이 아닌 정수 해 x_i의 개수를 셉니다.

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

문제

포켓몬 보호 협회는 전 세계의 포켓몬과 그 서식지를 보호한다. 최근 연구에서 $h$ 개 서식지의 데이터가 수집되었다. 한 서식지에는 여러 종의 포켓몬이 살 수 있다. 연구자는 각 종의 다리 수를 알고 있다. 포켓몬은 빠르고 숨는 데 매우 뛰어나서, 연구자는 각 서식지에 있는 다리의 총수만 파악할 수 있었다. 연구자는 각 종의 개체 수를 알아내지 못할 수도 있다는 점을 알고 있지만, 남은 불확실성이 얼마나 되는지 이해하고 싶어 한다. 관측된 다리 수와 일치하는 포켓몬 조합은 모두 몇 가지인가?

입력

첫 줄에 서식지의 수 $h$ ( $1 \le h \le 1\,024$ )가 주어진다. 다음 $h$ 개의 줄에는 각 서식지에 대한 설명이 주어진다. 각 줄은 두 정수 $t$ 와 $s$ ( $0 \le t \le 10^9$ , $1 \le s \le 3$ )로 시작한다. $t$ 는 다리의 총수이고, $s$ 는 서식지에 있는 종의 수다. 그 뒤에 $s$ 개의 정수 $l_i$ ( $1 \le l_i \le 16$ )가 주어지며, 이는 각 종의 다리 수다.

출력

각 서식지에서 가능한 포켓몬 조합의 수를 출력한다. $h$ 개의 줄을 출력하며, 각 줄에는 정수 하나를 쓴다.

예제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