Counting C-shaped and F-shaped Flower Planting Configurations

In his garden, Little C wants to plant flowers in the shape of the letters CCF. However, some cells in his garden contain pits where no flower can be planted. The garden can be represented as an n×m grid, with rows numbered from 1 to n and columns numbered from 1 to m. For each cell, a value of ai,j=1 indicates a pit while ai,j=0 indicates a cell where planting is possible.

A flower planting configuration is called a C-shaped configuration if there exist two row indices \(x_1,x_2\) (with \(1\le x_1,x_2\le n\)) and three column indices \(y_0,y_1,y_2\) (with \(1\le y_0,y_1,y_2\le m\)) such that: \[ x_1+1 < x_2, \quad y_0 < y_1,\, y_2 \le m, \] and the following cells are all free of pits and only these cells are used for planting:

• Row \(x_1\), columns from \(y_0\) to \(y_1\) (inclusive).
• Row \(x_2\), columns from \(y_0\) to \(y_2\) (inclusive).
• Column \(y_0\), rows from \(x_1\) to \(x_2\) (inclusive).

A configuration is called F-shaped if there exist three row indices \(x_1,x_2,x_3\) (with \(1\le x_1,x_2,x_3\le n\)) and three column indices \(y_0,y_1,y_2\) (with \(1\le y_0,y_1,y_2\le m\)) satisfying: \[ x_1+1 < x_2 < x_3, \quad y_0 < y_1,\, y_2 \le m, \] and the following cells are free of pits and only these cells are planted:

• Row \(x_1\), columns from \(y_0\) to \(y_1\) (inclusive).
• Row \(x_2\), columns from \(y_0\) to \(y_2\) (inclusive).
• Column \(y_0\), rows from \(x_1\) to \(x_3\) (inclusive).

Your task is to compute the number of valid C-shaped and F-shaped flower planting configurations modulo \(998244353\).

inputFormat

The first line contains two integers n and m --- the number of rows and columns in the garden.

Each of the next n lines contains m integers (either 0 or 1), where 1 indicates that the cell contains a pit and 0 indicates that the cell is available for planting.

outputFormat

Output two integers separated by a space: the number of valid C-shaped configurations and the number of valid F-shaped configurations, taken modulo \(998244353\).

sample

3 3
0 0 0
0 0 0
0 0 0

5 0