Công ty Advanced Ceiling Manufacturers (ACM) đang tiến hành phân tích các đặc tính của dòng sản phẩm mới mang tên Incredibly Collapse-Proof Ceilings (ICPCs). Một bộ ICPC bao gồm \(k\) lớp vật liệu, mỗi lớp có một giá trị chống sập (collapse resistance) khác nhau là một số nguyên dương.

ACM thực hiện phân tích bằng cách lấy các giá trị chống sập của các lớp, thứ tự từ lớp trên cùng đến lớp dưới cùng, và chèn chúng lần lượt vào một cây nhị phân. Các quy tắc để chèn một giá trị \(v\) vào cây như sau:

• Nếu cây đang trống, hãy đặt \(v\) làm gốc (root) của cây.
• Nếu cây không trống, hãy so sánh \(v\) với gốc của cây. Nếu \(v\) nhỏ hơn, hãy chèn \(v\) vào cây con bên trái (left subtree); nếu \(v\) lớn hơn, hãy chèn \(v\) vào cây con bên phải (right subtree).

ACM có một tập hợp các nguyên mẫu (prototypes) và họ muốn nhóm các nguyên mẫu có cùng hình dạng cây (tree shape) để phân tích cùng nhau.

Ví dụ: Xét 5 nguyên mẫu trần nhà, mỗi mẫu có 3 lớp. Hai mẫu có thứ tự giá trị là \((2, 7, 1)\) và \((3, 1, 4)\) sẽ tạo ra cùng một hình dạng cây, vì vậy ACM sẽ xếp chúng vào cùng một nhóm.

Yêu cầu

Cho một tập hợp các nguyên mẫu, nhiệm vụ của bạn là xác định có bao nhiêu hình dạng cây khác nhau được tạo ra.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) (\(1 \le n \le 50\)) là số lượng nguyên mẫu và \(k\) (\(1 \le k \le 20\)) là số lượng lớp trong mỗi nguyên mẫu.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(k\) số nguyên phân biệt (từ \(1\) đến \(10^6\)) là giá trị chống sập của các lớp theo thứ tự từ trên xuống dưới.

Output

• In ra một số nguyên duy nhất là số lượng hình dạng cây khác nhau.

Example

5 3
2 7 1
3 1 4
1 5 9
2 6 5
9 7 3

4

3 4
3 1 2 40000
3 4 2 1
33 42 17 23

2