Problem Description

The country of JOI is shaped like a rectangle divided into a grid of $ H $ rows and $ W $ columns. The vertical direction of JOI country is parallel to the north-south direction, and the horizontal direction is parallel to the east-west direction. The population of the cell in the $ i $-th row from the north ($1 \leq i \leq H$) and the $ j $-th column from the west ($1 \leq j \leq W$) is $ A_{i,j} $.

For administrative efficiency, JOI has decided to divide the entire country into two or more regions by drawing one or more boundary lines that satisfy the following conditions:

• The boundary lines are on the boundaries of the grid cells.
• The boundary lines are line segments connecting the north end to the south end or the east end to the west end of JOI country.

Given the population of each cell in JOI country, create a program to determine how many ways there are to divide the country such that all regions have equal population.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ A_{1,1} $ $ A_{1,2} $ $\cdots$ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $\cdots$ $ A_{2,W} $ $\vdots$ $ A_{H,1} $ $ A_{H,2} $ $\cdots$ $ A_{H,W} $

Output Format

Output a single line to the standard output, the number of ways to divide the country such that all regions have equal population.

Sample Input and Output

Sample Input #1

2 3
10 10 20
10 10 20

Sample Output #1

3

Sample Input #2

1 4
2 1 1 2

Sample Output #2

2

Sample Input #3

3 3
2 9 4
7 5 3
6 1 8

Sample Output #3

2

Sample Input #4

1 1
10000

Sample Output #4

0

Notes/Hints

Constraints

• $1 \leq H \leq 50$.
• $1 \leq W \leq 50$.
• $1 \leq A_{i,j} \leq 100,000$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
• All input values are integers.

Subtasks

1. ($ 12 $ points) $ H = 1 $.
2. ($ 26 $ points) $H \leq 6$, $W \leq 6$.
3. ($ 62 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test input data corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked from the "My Score Status" tab in the "Submission Results".

见题面 Input 部分

见题面 Output 部分