你有一个 $H$ 行 $W$ 列的网格。每个单元格包含以下 11 种字符之一：加法运算符 '+'、乘法运算符 '*' 或 1 到 9 之间的数字。

从左上角单元格到右下角单元格，可以通过向右或向下移动 $H + W - 2$ 次到达。我们将一条路径的值定义为通过按顺序连接路径上所有单元格中的字符所得到的数学表达式的计算结果。你的任务是计算所有可能路径的值之和。由于总和可能很大，请输出其对 $M$ 取模的结果。

题目保证左上角和右下角的单元格包含数字。此外，如果两个单元格共享一条边，则其中至少有一个包含数字。换句话说，从路径中获得的每个表达式在数学上都是有效的。

输入格式

第一行包含三个整数 $H$、$W$ 和 $M$ ($1 \le H, W \le 2000, 2 \le M \le 10^9$)。接下来的 $H$ 行表示网格中的字符。$a_{i,j}$ 表示第 $i$ 行第 $j$ 列单元格中的字符。每个 $a_{i,j}$ 都是 '+'、'*' 或 1 到 9 之间的数字。$a_{1,1}$ 和 $a_{H,W}$ 均为数字。如果两个单元格共享一条边，则其中至少有一个包含数字。

输出格式

输出所有可能路径的值之和，对 $M$ 取模。

样例

输入 1

2 3 1000
3*1
+27

输出 1

162

输入 2

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

输出 2

2159570