Route Calculator Returns

Time limit2sMemory limit512 MB

Summary

Sum the values of every right-or-down grid path, where each path reads as an expression with + and * and digits, modulo M.

Level: Medium7 of 10
Topics: Dynamic programming, Math, String
Solved: No attempts yet

Problem

The grid has $H$ rows and $W$ columns. Each cell contains one of 11 characters: an addition operator '+', a multiplication operator '*', or a digit from 1 to 9.

A path starts at the top-left cell and ends at the bottom-right cell, moving only right or down. The value of a path is the result of the expression formed by concatenating the characters in the cells on the path, in order. Find the sum of the values of all possible paths. Since the sum can be large, print it modulo $M$ .

The top-left and bottom-right cells always contain digits. Also, at least one of any two cells that share an edge contains a digit. So every expression obtained from a path is a valid expression.

Input

The first line contains three integers $H$ , $W$ , and $M$ ( $1 \le H, W \le 2000$ , $2 \le M \le 10^9$ ). The next $H$ lines describe the grid. $a_{i,j}$ is the character in the cell at row $i$ and column $j$ . Each $a_{i,j}$ is '+', '*', or a digit from 1 to 9. Both $a_{1,1}$ and $a_{H,W}$ are digits. At least one of any two cells that share an edge is a digit.

Output

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

Examples2

Example 1
Input
```
2 3 1000
3*1
+27
```
Expected output
```
162
```

Example 2

Input

4 4 3000000
24+7
*23*
9+48
*123

Expected output