Kế hoạch tiến hoá

Trên vùng Himalaya có $n$ phòng tập (gym), được đánh số từ $1$ đến $n$. Trong vùng có $m$ loại Pokémon phân biệt, đánh số từ $1$ đến $m$. Phòng tập thứ $i$ chứa $g_i$ con Pokémon (có thể có nhiều con cùng loại).

Tại một trại tiến hoá đặc biệt, người ta sẽ áp dụng cùng một kế hoạch tiến hoá cho mọi Pokémon. Kế hoạch tiến hoá là một hoán vị $f$ của tập $\{1,2,\dots ,m\}$: mỗi Pokémon có loại $x$ sẽ tiến hoá thành Pokémon có loại $f(x)$. Lưu ý rằng $f$ là một hoán vị nên hai loại khác nhau luôn cho ra hai loại khác nhau, còn một loại có thể tiến hoá thành chính nó.

Theo quy ước, một kế hoạch tiến hoá được xem là hợp lệ nếu sau khi tiến hoá tất cả Pokémon, trong mỗi phòng tập và với mỗi loại Pokémon, số lượng Pokémon loại đó trước và sau khi tiến hoá là như nhau.

Hãy đếm số kế hoạch tiến hoá hợp lệ. Vì kết quả có thể rất lớn, in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng số nguyên $g_i$ — số Pokémon trong phòng tập thứ $i$, theo sau là $g_i$ số nguyên biểu thị loại của các Pokémon đó (mỗi số nằm trong đoạn $[1,m]$).

Dữ liệu ra

Một số nguyên duy nhất — số kế hoạch tiến hoá hợp lệ, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le {10}^6$
• $1\le g_i\le {10}^5$
• Tổng $\sum g_i\le 5·{10}^5$.

Ví dụ