창고

어느 핀란드 첨단 기술 회사가 큰 직사각형 창고를 가지고 있다. 창고에는 작업자 한 명과 관리자 한 명이 있다. 창고의 네 변은 둘레를 따라 순서대로 왼쪽, 위, 오른쪽, 아래라고 부른다. 창고 바닥은 행과 열로 나뉘어 같은 크기의 정사각형 칸들로 이루어진다. 행은 위에서부터 1, 2, ... 로 번호를 매기고, 열은 왼쪽에서부터 1, 2, ... 로 번호를 매긴다.

창고에는 귀중한 기술 장비를 보관하는 컨테이너들이 있다. 각 컨테이너는 서로 다른 식별 번호를 가지며 한 칸을 차지한다. 창고가 매우 커서, 앞으로 도착할 컨테이너의 총 개수는 행의 수보다 적고 열의 수보다도 적다. 컨테이너는 창고에서 꺼내지 않으며, 가끔 새 컨테이너가 도착한다. 창고의 입구는 왼쪽 위 모서리에 있다.

작업자는 식별 번호로 컨테이너를 쉽게 찾을 수 있도록 왼쪽 위 모서리 근처에 다음 방법으로 컨테이너를 배치한다.

다음에 넣을 컨테이너의 식별 번호를 $k$ 라 하자(줄여서 컨테이너 $k$). 작업자는 첫 번째 행을 왼쪽부터 훑으며 식별 번호가 $k$ 보다 큰 첫 번째 컨테이너를 찾는다. 그런 컨테이너가 없으면, 컨테이너 $k$ 를 그 행에 이미 있던 가장 오른쪽 컨테이너 바로 뒤에 놓는다. 만약 그런 컨테이너 $l$ 을 찾으면, 컨테이너 $l$ 을 컨테이너 $k$ 로 교체하고, 밀려난 컨테이너 $l$ 을 같은 방법으로 다음 행에 넣는다. 작업자가 컨테이너가 하나도 없는 행에 도달하면, 그 행의 가장 왼쪽 칸에 컨테이너를 놓는다.

컨테이너 3, 4, 9, 2, 5, 1 이 이 순서대로 창고에 도착했다고 하자. 그러면 컨테이너의 배치는 다음과 같다.

1 4 5
2 9
3

관리자가 작업자에게 와서 다음과 같은 대화를 나눈다.

관리자: 컨테이너 5가 컨테이너 4보다 먼저 도착했나요?

작업자: 아니요, 그건 불가능합니다.

관리자: 오, 그러면 배치만 보고 컨테이너의 도착 순서를 알 수 있겠군요.

작업자: 보통은 아닙니다. 예를 들어 지금 창고에 있는 컨테이너들은 3, 2, 1, 4, 9, 5 순서로 도착했을 수도 있고, 3, 2, 1, 9, 4, 5 순서일 수도 있으며, 그 밖에 14가지 다른 순서로 도착했을 수도 있습니다.

관리자는 작업자가 자신보다 훨씬 똑똑해 보이는 것이 달갑지 않아 자리를 떠난다. 당신은 관리자를 도와, 주어진 컨테이너 배치에 대해 그것을 만들어 낼 수 있는 도착 순서가 몇 가지인지 계산하는 프로그램을 작성해야 한다.

첫째 줄에 정수 $R$ 이 주어진다. $R$ 은 컨테이너가 들어 있는 행의 개수이다. 이어지는 $R$ 개의 줄에는 위에서부터 행 $1, ..., R$ 에 대한 정보가 주어진다. 각 줄은 먼저 정수 $M$ 으로 시작하는데, $M$ 은 그 행에 있는 컨테이너의 개수이다. 그 뒤에 $M$ 개의 정수가 이어지며, 이는 그 행에 왼쪽부터 놓인 컨테이너들의 식별 번호이다. 모든 컨테이너 식별 번호 $I$ 는 $1 \le I \le 50$ 을 만족한다. 창고에 있는 컨테이너의 총 개수를 $N$ 이라 하면 $1 \le N \le 13$ 이다.

주어진 배치를 만들어 낼 수 있는 서로 다른 도착 순서의 개수를 정수 하나로 출력한다.