题目描述

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$.

2 2
44
9*

346

2 3
314
28*

601

4 6
314159
2*6535
*89793
238*4*

37655

18 20
65929431919981098712
34182289733359024486
*5999742744659484782
03563591172305229098
55764088882794210744
65542986390400199274
24954674699538357427
65448003011829165060
0570520*394989799204
21113635765787241691
24382969673042349665
04571518994293776944
42950768895299998684
02191975238817773041
08629513210946362875
91583470151322043009
00337992511803056114
59396973995193492513

78257625

提示

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 :::