64. 達克妮絲的裝備

Problem Description

因為上次出任務賺了不少金，達克妮絲想要組一個新的套裝；由於某些原因，她想要這個套裝的防禦力越低越好。一個套裝的防禦力取決於他是由幾個配件組合而成，比方說三個配件組成的套裝防禦力 $= 3$。

但是基於十字騎士工會的規定，為了騎士自身安全和騎士的職業名譽，一個騎士出任務時必須妥善地蓋住身上每個指定部位。所以達克妮絲請求你的幫助：以現有的配件，請問有幾種套裝組合能滿足達克妮絲和工會的要求？

Input Format

每筆測資會有 $N + 1$ 行，第一行包含兩個整數 $N$ $K$ ，分別代表：

$N$：可挑選的配件有幾種

$K$：身上有多少部位需要覆蓋

接著有 $N$ 行，分別表示一個配件。在其中的第 $i$ 行，會先有一個整數 $P_i$ ，表示這個配件可以覆蓋到不同的身體部位數；接著會有 $P_i$ 個不同的整數 ( 範圍： $1$ ~ $K$ ) 分別代表這些身體部位。

Input Constraints

$ 1 \leq N \leq 5000 $

$ 1 \leq K \leq 10 $

對任意 $i$： $ 1 \leq P_i \leq K $

Output Format

如果現有的配件湊不出符合工會要求的套裝，輸出 -1 並結束即可。否則輸出兩個整數 $L$ $C$ ，分別代表：

$L$：想拼出一個符合工會要求的套裝，最低的防禦力可以是多少

$C$：有多少種同時滿足 (1) 防禦力 $ = L$ (2) 覆蓋全身 兩項要求的組合

由於 $C$ 可能數字龐大，請先 mod 1000000007 後輸出。

Sample IO

Sample In 1

4 3
1 1
1 2
1 3
2 2 3

Sample Out 1

2 1

Sample In 2

4 5
3 1 2 3
3 2 3 4
3 3 4 5
2 1 5

Sample Out 2

2 2

Sample In 3

3 4
2 1 2
2 2 3
1 1

Sample Out 3

-1

Sample Explanation

在第一筆範例測資，我們可以用第一和第四個配件湊出一個防禦力 $= 2$ 的套裝；顯然沒有其他能湊出同樣防禦力的合法套裝，也不可能湊出防禦力更低的合法套裝。

Score Distribution

Test case #1~2 : $N \leq 20$ ( score: 20 )

Test case #3~5 : $N \leq 5000$ ( score: 80 )

Judge Setting

run-time limit: 10000 ms
memory limit: 256000000 byte
測資數量: 5