P15723 [JAG 2023 Summer Camp #3] Digit-only subrectangles

There are $H$ rows and $W$ columns of square cells. Each cell has either a digit or an asterisk ('*'). The cell at the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$. In this problem we consider subrectangles, each of which is the set of cells which forms a rectangle. More precisely, a set of cells $S$ is a subrectangle if there are four integers $t$, $b$, $l$ and $r$ such that $1 \leq t \leq b \leq H$, $1 \leq l \leq r \leq W$ and $S = \{(i, j) \mid t \leq i \leq b \land l \leq j \leq r\}$. A subrectangle is digit-only if every cell in the subrectangle has a digit. The score of a digit-only subrectangle is defined as the square of the sum of digits in cells in the subrectangle. Your task is to calculate the sum of scores of all digit-only subrectangles. Since the answer may be large, output it modulo $998,244,353$.

The input consists of a single test case of the following format. $$ \begin{aligned} &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} \end{aligned} $$ The first line consists of two integers $H$ and $W$, which satisfy $1 \leq H \leq 2,000$ and $1 \leq W \leq 2,000$. Each of the following $H$ lines consists of $W$ characters. Here, $A_{i,j}$ is the character in the cell $(i, j)$, and it is either a digit between $0$ and $9$, inclusive, or an asterisk ('*'). It is guaranteed that there is at least one digit-only subrectangle.

Output in a line the sum of scores of all digit-only subrectangles modulo $998,244,353$.

In Sample Input 1, there are five digit-only subrectangles as illustrated below. The sum of their scores is $4^2 + 4^2 + 9^2 + (4 + 4)^2 + (4 + 9)^2 = 346$. :::align{center}  Figure F.1. Digit-only subrectangles in Sample Input 1 :::