32531번 - 래환이의 수강신청 대작전

문제

한과영에는 $N$개의 과목 $S_1, S_2, \cdots, S_N$이 있고, 래환이와 1ドル$번부터 $M$번까지의 학번이 부여된 $M$명의 학생들이 있다. 모든 학생은 최소 하나 이상의 과목을 신청해야 하며, 신청한 과목이 완전히 동일한 학생 쌍은 존재해서는 안 된다.

래환이는 과목 $S_N$을 신청할 경우 같이 듣게 될 학생들의 조합이 궁금해졌다. 과목 $S_1, S_2, \cdots, S_{N-1}$을 신청하는 학생들의 학번이 주어졌을 때, 과목 $S_N$을 신청하는 학생들의 가능한 조합의 가짓수를 구하는 프로그램을 작성하시오. 단, 래환이의 신청 여부는 고려하지 않으며, 오직 $M$명의 학생들의 조합만 고려한다. 또한, 아무도 과목 $S_N$을 신청하지 않는 경우도 가능하다.

입력

첫 번째 줄에는 두 개의 정수 $N$$(2 \le N \le 30)$과 $M$$(1 \le M \le 30)$이 주어진다.

다음 $(N-1)$개의 줄 중 $i$번째 줄에는 $S_i$를 신청하는 학생 수와 $S_i$를 신청하는 학생들의 학번이 공백으로 구분되어 주어진다. 만약 $S_i$를 신청하는 학생이 존재하지 않는다면 해당 줄에 0ドル$ 하나만 주어진다.

출력

과목 $S_N$을 신청하는 학생들의 가능한 조합의 가짓수를 출력한다. 만약 가능한 조합이 존재하지 않는다면 0ドル$을 출력한다.

제한

힌트