006 - 伝言ゲーム

時間制限 1 秒 / メモリ制限 256 MB / 得点 8 / x 0 /


TLE
1sec
MLE
256MB
得点
8

問題

PCK君は友達の誕生日のパーティーの余興として伝言ゲームを企画しています。
パーティーへの参加者のうち5人が横一列に並び、伝言ゲームにチャレンジします。最初に左端の人にメッセージが伝えられ、それを右隣の人に順に伝えていき、右端の人に正しくメッセージが伝わればチャレンジが成功し、5人に景品が与えられます。ただし、メッセージを正しく伝えるためには、話し手と聞き手が共通の言語を使える必要があります。
パーティーには世界中から友人が集まります。PCK君は景品の予算を見積もるために、伝言ゲームが成功する可能性のある参加者の並び方の数を計算することにしました。
パーティーに参加する人数、各参加者が使える言語のリストが与えられたとき、伝言ゲームが成功する可能性のある参加者の並び方の数を求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$info_1$
$info_2$
  $\vdots$
$info_N$

1行目にパーティーへの参加者の数$N$($5 \leq N \leq 200$)が与えられる。続く$N$行に$i$番目の参加者が使用できる言語の情報$info_i$与えられる。$info_i$は以下の形式で与えられる。

$k$ $l_1$ $l_2$ ... $l_k$
$k$($1 \leq k \leq 200$)はこの参加者が使うことができる言語の数を表す。$l_i$はこの参加者が使うことができる言語を表す文字列(2文字の英小文字)である。ただし、同じ参加者が使える言語に重複は無い($i ≠ j$ならば$l_i ≠ l_j$)。

出力

伝言ゲームが成功する可能性のある参加者の並び方の数を1行に出力する。

入出力例

入力例1

5
2 ja en
2 ja en
2 ja en
2 ja en
2 ja en

出力例1

120

入力例2

6
1 ja
3 ja en ch
2 en fr
2 ve fr
3 ch ve po
1 po

出力例2

8