천장 함수

ACM(Advanced Ceiling Manufacturers)은 새로 내놓은 초강력 붕괴 방지 천장(ICPC) 시리즈의 성질을 분석한다. ICPC 천장 하나는 여러 층의 재료를 쌓아 만들고, 각 층의 붕괴 저항값은 양의 정수이며 층마다 값이 서로 다르다. ACM이 하려는 분석은 층의 붕괴 저항값을 이진 탐색 트리에 저장한 뒤, 그 트리의 모양이 천장 전체의 품질과 관계가 있는지 확인하는 것이다. 안 될 이유도 없으니까.

ACM은 붕괴 저항값을 위쪽 층부터 아래쪽 층까지 순서대로 읽어서 트리에 하나씩 삽입한다. 값 $v$를 삽입하는 규칙은 다음과 같다.

• 트리가 비어 있으면 $v$를 트리의 루트로 삼는다.
• 트리가 비어 있지 않으면 $v$를 루트와 비교한다. $v$가 더 작으면 루트의 왼쪽 서브트리에 삽입하고, 그렇지 않으면 오른쪽 서브트리에 삽입한다.

ACM은 실제로 붕괴시켜 분석할 천장 시제품을 여러 개 가져다 놓았다. 트리 모양이 같은 시제품끼리 묶어서 그룹 단위로 분석한다.

아래 첫 번째 예제에 나오는 세 층짜리 시제품 다섯 개를 보자. 첫 번째 시제품은 위층의 붕괴 저항값이 2, 가운데 층이 7, 아래층이 1이다. 두 번째 시제품의 층은 3, 1, 4인데 두 시제품이 만드는 트리 모양은 같으므로 ACM은 이 둘을 함께 분석한다.

시제품 집합이 주어질 때 이들이 만드는 트리 모양이 몇 가지인지 구하라.

위 그림은 첫 번째 예제의 시제품이 만드는 네 가지 트리 모양이다.

첫째 줄에 분석할 천장 시제품의 개수 $n$ ($1 \le n \le 50$)과 각 시제품의 층 수 $k$ ($1 \le k \le 20$)가 주어진다.

다음 $n$개의 줄에 시제품이 한 줄에 하나씩 주어진다. 각 줄에는 $1$ 이상 $1\,000\,000$ 이하의 서로 다른 정수 $k$개가 위층부터 아래층 순서로 주어지며, 이 값이 각 층의 붕괴 저항값이다.

서로 다른 트리 모양의 개수를 출력한다.