Đất nước JOI có hình chữ nhật, được chia thành \(H\) hàng và \(W\) cột ô vuông. Chiều dọc của đất nước song song với hướng bắc–nam, còn chiều ngang song song với hướng đông–tây. Ô ở hàng thứ \(i\) tính từ phía bắc (\(1 \le i \le H\)) và cột thứ \(j\) tính từ phía tây (\(1 \le j \le W\)) có dân số là \(A_{i,j}\) người.

Để việc quản lý hiệu quả hơn, đất nước JOI quyết định chia toàn bộ lãnh thổ thành ít nhất hai khu vực bằng cách kẻ ít nhất một đường ranh giới. Mỗi đường ranh giới phải thỏa mãn cả hai điều kiện sau:

• Nằm trên các đường phân cách giữa các ô.
• Là một đoạn thẳng nối từ biên phía bắc đến biên phía nam của đất nước, hoặc nối từ biên phía đông đến biên phía tây của đất nước.

Cho dân số của từng ô, hãy đếm số cách chia sao cho tất cả các khu vực đều có dân số bằng nhau.

Dữ liệu vào

Dữ liệu vào có dạng:

H W
A_1,1 A_1,2 ... A_1,W
A_2,1 A_2,2 ... A_2,W
...
A_H,1 A_H,2 ... A_H,W

Dữ liệu ra

In ra một dòng chứa số cách chia sao cho tất cả các khu vực đều có dân số bằng nhau.

Ràng buộc

• \(1 \le H \le 50\).
• \(1 \le W \le 50\).
• \(1 \le A_{i,j} \le 100\,000\) (\(1 \le i \le H\), \(1 \le j \le W\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. 12 điểm: \(H=1\).
2. 26 điểm: \(H \le 6\), \(W \le 6\).
3. 62 điểm: Không có ràng buộc bổ sung.

Ví dụ

2 3
10 10 20
10 10 20

3

1 4
2 1 1 2

2

3 3
2 9 4
7 5 3
6 1 8

2

1 1
10000

0

Nguồn

Đề bài Land Division, JOI 2021/2022, vòng loại thứ hai, bài 3 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.