30371번 - 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ドル \le t \le b \le H,ドル 1ドル \le l \le r \le W$ and $S = \{(i,j) \mid t \le i \le b \wedge l \le j \le 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.

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

The first line consists of two integers $H$ and $W,ドル which satisfy 1ドル \le H \le 2,000円$ and 1ドル \le W \le 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$.

Figure F.1. Digit-only subrectangles in Sample Input 1