Việt và Hàn đang cùng điều hành một nhà hàng tiêu chuẩn năm sao. Tại đây, Việt và Hàn nhập về \(K\) loại nguyên liệu chất lượng cao và chuyên chế biến các món ăn từ \(K\) nguyên liệu này. Các nguyên liệu được đánh số từ \(0\) đến \(K - 1\).

Nhà hàng của Việt và Hàn có tất cả \(N\) tổ đầu bếp. Các tổ được đánh số từ \(0\) đến \(N - 1\). Mỗi tổ đầu bếp được trang bị các dụng cụ và có kỹ năng chế biến khác nhau. Cụ thể, tổ đầu bếp thứ \(i\) có bộ chỉ số năng lực chế biến gồm \(K\) số nguyên \(\ell_i^{(0)}, \ell_i^{(1)}, \dots, \ell_i^{(K-1)}\), trong đó \(\ell_i^{(j)}\) là năng lực chế biến nguyên liệu thứ \(j\).

Khi nhận đặt hàng một món ăn, Việt và Hàn sẽ tính độ khó của việc xử lý các loại nguyên liệu của món ăn đó, để giao cho tổ đầu bếp thích hợp. Như vậy, mỗi món ăn được đặc tả bởi dãy chỉ số thành phần gồm \(K\) số nguyên dương \(r^{(0)}, r^{(1)}, \dots, r^{(K-1)}\) với ý nghĩa: Tổ bếp thứ \(i\) chế biến được món ăn này khi và chỉ khi \(r^{(j)} \le \ell_i^{(j)}\) với mọi \(0 \le j < K\).

Mùa cao điểm du lịch của Đà Nẵng sắp đến. Để quảng bá hình ảnh địa phương, thành phố sẽ tổ chức nhiều lễ hội ẩm thực, và một số tổ đầu bếp tại nhà hàng của Việt và Hàn sẽ được điều động tham gia những sự kiện này. Khi đó, có một vấn đề phát sinh: nhà hàng có thể sẽ không phục vụ được một số món ăn nữa, vì mọi tổ đầu bếp chế biến được những món ăn này đều đã bị điều động.

Nhằm tránh bị động trước diễn biến này, Việt và Hàn cần đánh giá mức độ rủi ro của các kịch bản điều động đầu bếp. Cụ thể, gọi \(S\) là một tập hợp các tổ đầu bếp (tức \(S \subset \{0, 1, \dots, N - 1\}\)), dãy chỉ số thành phần \(r^{(0)}, r^{(1)}, \dots, r^{(K-1)}\) được gọi là phụ thuộc hoàn toàn vào \(S\) nếu như:

• Trong \(N\) tổ bếp của nhà hàng, có ít nhất một tổ chế biến được món ăn có dãy chỉ số này.
• Không tồn tại bất kỳ tổ bếp nào không thuộc \(S\) chế biến được món ăn có dãy chỉ số này.

Độ rủi ro ứng với tập hợp \(S\) là số dãy chỉ số thành phần phụ thuộc hoàn toàn vào \(S\).

Việt và Hàn muốn có phương án đối phó với mọi kịch bản có thể xảy ra, nên họ muốn biết độ rủi ro ứng với tất cả \(2^N - 1\) tập con khác rỗng của tập hợp \(N\) tổ đầu bếp. Các bạn hãy giúp Việt và Hàn tính các giá trị này nhé.

Lưu ý: Trong bài tập này, ta định nghĩa khái niệm mã biểu diễn tập hợp như sau: Gọi \(S\) là một tập hợp hữu hạn các số tự nhiên, mã biểu diễn của \(S\) là số tự nhiên \(x\) thoả mãn: Với mọi số tự nhiên \(t\),

• Nếu \(t \in S\), \(\lfloor \frac{x}{2^t} \rfloor\) là một số lẻ.
• Nếu \(t \notin S\), \(\lfloor \frac{x}{2^t} \rfloor\) là một số chẵn.

Có thể chứng minh được rằng, với mọi số nguyên \(x \in \{1, 2, \dots, 2^N - 1\}\), có một và chỉ một tập hợp \(S \subset \{0, 1, \dots, N - 1\}\) có mã biểu diễn là \(x\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N, K \le 20\)) lần lượt là số tổ đầu bếp và số loại nguyên liệu của nhà hàng.
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa \(K\) số nguyên \(\ell_i^{(0)}, \ell_i^{(1)}, \dots, \ell_i^{(K-1)}\) (\(1 \le \ell_i^{(j)} \le 10^9\)) là bộ chỉ số năng lực của tổ bếp thứ \(i\).

Output

• In ra trên một dòng duy nhất \(2^N - 1\) số nguyên \(a_1, a_2, \dots, a_{2^N - 1}\), trong đó giá trị \(a_x\) được xác định như sau:
  • Gọi \(S\) là tập hợp thoả mãn \(S \subset \{0, 1, \dots, N - 1\}\) và \(S\) có mã biểu diễn là \(x\).
  • Đặt \(b_S\) là độ rủi ro ứng với tập hợp \(S\).
  • \(a_x\) là phần dư của \(b_S\) khi chia cho \(10^9 + 7\).

Example

3 2
2 4
4 2
3 3

2 2 4 1 5 5 13

Scoring

• Subtask 1 (20 điểm): \(N \le 10, K \le 5\).
• Subtask 2 (20 điểm): \(N \le 15, K \le 15\).
• Subtask 3 (20 điểm): \(N \le 20, K = 2\).
• Subtask 4 (40 điểm): Không có ràng buộc nào thêm.