Ghép Cặp Tương Thích · canuc80k1503

Có $N$ người ở nhóm $A$ và $N$ người ở nhóm $B$ , mỗi nhóm được đánh số từ $1$ đến $N$ . Ma trận nhị phân $a$ cho biết những cặp có thể ghép: $a_{i} [j] = 1$ khi người $i$ của nhóm $A$ tương thích với người $j$ của nhóm $B$ .

Một cách ghép hoàn hảo phải ghép mỗi người đúng một lần và chỉ sử dụng các cặp tương thích.

Hãy đếm số cách ghép hoàn hảo. Do kết quả có thể rất lớn, in phần dư theo modulo $1000000007$ .

Input

Dòng đầu chứa số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng chứa $N$ số $0$ hoặc $1$ , mô tả ma trận $a$ .

Output

In số cách ghép hoàn hảo modulo $1000000007$ .

Constraints

$1 \leq N \leq 21$ .
$a_{i, j} \in {0, 1}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 9$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai cách ghép theo chỉ số nhóm $B$ là $(1, 2, 3)$ và $(2, 3, 1)$ . Mọi hoán vị còn lại đều chứa ít nhất một cặp có giá trị $0$ .

Ý tưởng: Dùng mask để biểu diễn tập người của nhóm B đã được dùng. Khi mask có k bit 1, người tiếp theo cần ghép ở nhóm A là người thứ k (đánh số từ 0 trong mã).
Ý tưởng: dp[mask] là số cách ghép k người đầu tiên của nhóm A với đúng các cột trong mask. Từ trạng thái này, thử mọi cột chưa dùng và tương thích với hàng k, rồi cộng vào trạng thái mới; mọi phép cộng được lấy modulo.
Ý tưởng: Chứng minh đúng. Mỗi ghép hoàn hảo xác định duy nhất dãy cột được chọn cho các hàng 0,1,...,N-1. DP sinh đúng dãy đó vì ở lớp có k bit chỉ xử lý hàng k, chỉ chọn cột chưa dùng và chỉ đi qua ô tương thích. Ngược lại, mọi đường từ mask rỗng đến mask đầy chọn mỗi cột đúng một lần, nên tạo một ghép hoàn hảo hợp lệ. Vì vậy phép cộng đếm không thiếu và không trùng.
Ý tưởng: Độ phức tạp. O(N·2^N) thời gian và O(2^N) bộ nhớ.