20632번 - Route Calculator Returns 다국어

문제

You have a grid with $H$ rows and $W$ columns. Each cell contains one of the following 11 characters: an addition operator '+', a multiplication operator '*', or a digit between 1 and 9.

There are paths from the top-left cell to the bottom-right cell by moving right or down $H+W-2$ times. Let us define the value of a path by the evaluation result of the mathematical expression you can obtain by concatenating all the characters contained in the cells on the path in order. Your task is to compute the sum of values of any possible paths. Since the sum can be large, find it modulo $M$.

It is guaranteed the top-left cell and the bottom-right cell contain digits. Moreover, if two cells share an edge, at least one of them contains a digit. In other words, each expression you can obtain from a path is mathematically valid.

입력

The first line of the input consists of three integers $H,ドル $W$ and $M$ (1ドル \le H,W \le 2000,ドル 2ドル \le M \le 10^9$). The following $H$ lines represent the characters on the grid. $a_{i,j}$ represents the character contained in the cell at the $i$-th row and $j$-th column. Each $a_{i,j}$ is either '+', '*', or a digit between 1 and 9. $a_{1,1}$ and $a_{H,W}$ are both digits. If two cells share an edge, at least one of them contain a digit.

출력

Print the sum of values of all possible paths modulo $M$.

제한

힌트