Floral Garden
本题没有可用的提交语言。
Description
Legendary Huron is in charge of building the floral garden in Huron Park, the new public park in Huronland. The floral garden can be represented as a matrix of flowers consisting of $n$ rows and $m$ columns, where the flower at the intersection of the $i$-th row and the $j$-th column has beauty $a_{i,j}$.
The government of Huronland will take a photo of the floral garden to promote tourism in Huron Park. The photo will consist of a submatrix of the floral garden. In other words, the flowers that are located between the rows $x_1$ and $x_2$ and between the columns $y_1$ and $y_2$, for some $1 \leq x_1 \leq x_2 \leq n$ and $1 \leq y_1 \leq y_2 \leq m$, will appear in the photo.
Legendary Huron defines the beauty of a photo to be the product of the sum of the maximum beauty in every row of the photo and the sum of the maximum beauty in every column of the photo. More formally, let $r_i$ be the maximum beauty in the $i$-th row of the photo, and let $c_j$ be the maximum beauty in the $j$-th column of the photo. The beauty of the photo is defined as $(r_1 + r_2 + \dots + r_f)(c_1 + c_2 + \dots + c_g)$, where $f$ is the number of rows and $g$ is the number of columns.
It has not been decided which submatrix will be photo, but Legendary Huron wants to know the sum of all possible beauties. Help him find the sum of the beauty of all possible photos of the floral garden. Since the answer can be too large, print it modulo $998244353$.
The first line contains two integers $n$ and $m$ $(1 \leq n,m \leq 1000)$ — the number of rows and columns in the floral garden.
The following $n$ lines contains the beauties of the flowers. The $(i+1)$-th line contains $m$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($|a_{i,j}| \leq 10^9$) — the beauty of the flowers in the $i$-th row.
Print the answer modulo $998244353$.
Input
The first line contains two integers $n$ and $m$ $(1 \leq n,m \leq 1000)$ — the number of rows and columns in the floral garden.
The following $n$ lines contains the beauties of the flowers. The $(i+1)$-th line contains $m$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($|a_{i,j}| \leq 10^9$) — the beauty of the flowers in the $i$-th row.
Output
Print the answer modulo $998244353$.
2 2
1 2
3 4
5 3
3 4 8
-3 -4 -8
4 5 1
-1 3 10
0 0 0
142
6293