Ánh Minh rất thích chơi cờ vua. Cô ấy đã tạo ra ~n~ bàn cờ có kích thước ~k \times k~, được biểu diễn dưới dạng dãy ~a~ hai chiều với đặc điểm như sau:

• ~a[i][j] = 0~: Ô đó không có quân cờ;
• ~a[i][j] = 1~: Ô đó có quân cờ.

Tuy nhiên, sau khi chơi, có thể có các bàn cờ giống nhau. Ánh Minh cần các bạn đếm số cặp bàn cờ giống nhau. Hai bàn cờ được coi là giống nhau khi một bàn cờ có thể xoay sao cho ra được bàn cờ còn lại.

Input Specification: Data taken from CHESS.INP

• Dòng đầu tiên gồm hai số ~n~ và ~k~ ~(n \le 5 \times 10^4; k \le 30)~.
• Sau đó là ~n~ blocks mô phỏng bàn cờ:
  • Để dễ biểu diễn, bàn cờ sẽ được mô phỏng với mảng ~b~ gồm ~n~ số ~x~ ~(x < 2^k)~;
  • Bàn cờ sẽ được biểu diễn dựa vào mảng ~b~ như sau: Nếu bit thứ ~j~ từ trái sang của phần tử thứ ~i~ trong mảng ~b~ bằng ~1~ thì ~a[i][j] = 1~, ngược lại đặt ~a[i][j] = 0~.

Output Specification: Data written in CHESS.OUT

• Xuất ra duy nhất một số là số cặp bàn cờ vua giống nhau.

Subtasks

• Subtask #1 [20%]: ~n \le 5000; k \le 3~.
• Subtask #2 [20%]: ~k \le 8~.
• Subtask #3 [20%]: ~n \le 500~.
• Subtask #4 [20%]: ~n \le 5000~.
• Subtask #5 [20%]: Không có ràng buộc gì thêm.

Sample Cases

Input #1:

4 3
2 5 0
2 1 2
6 1 4
5 1 2

Output #1:

2

Explanation #1:

• Bàn cờ thứ nhất:

010
101
000

• Bàn cờ thứ hai:

010
001
010

• Bàn cờ thứ ba:

110
001
100

• Bàn cờ thứ tư:

101
001
010