Kế hoạch tiến hoá

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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 \leq n \leq 10^{5}$
$1 \leq m \leq 10^{6}$
$1 \leq g_{i} \leq 10^{5}$
Tổng $\sum g_{i} \leq 5 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
2 3 2 1 2 2 2 3	1	Chỉ có duy nhất kế hoạch $f$ giữ nguyên tất cả các loại.
1 3 3 1 2 3	6	Mọi hoán vị của ${1, 2, 3}$ đều hợp lệ vì phòng tập có đúng một con của mỗi loại.
2 4 2 1 2 3 2 3 4	2	Có thể giữ nguyên hoặc đổi vai trò của loại $3$ và $4$ (cả hai chỉ xuất hiện một lần trong cùng phòng tập thứ $2$ ).
3 7 2 1 2 2 3 4 3 5 6 7	24	Trong mỗi cặp/bộ ba xuất hiện cùng một bộ phòng tập với cùng số lượng, các loại có thể hoán đổi tự do. Hai loại đầu cho $2!$ , hai loại giữa cho $2!$ , ba loại cuối cho $3!$ , tổng cộng $2 \cdot 2 \cdot 3! = 24$ .

Bình luận

Không có bình luận tại thời điểm này.