경로 계산기 반환

격자는 $H$행 $W$열로 이루어져 있다. 각 칸에는 다음 11가지 문자 중 하나가 적혀 있다. 덧셈 연산자 '+', 곱셈 연산자 '*', 또는 1부터 9까지의 숫자이다.

왼쪽 위 칸에서 시작해 오른쪽 아래 칸에서 끝나는 경로가 있다. 이동은 오른쪽 또는 아래로만 할 수 있다. 경로의 값은 경로에 놓인 칸의 문자를 순서대로 이어 붙여 얻은 수식을 계산한 결과이다. 가능한 모든 경로의 값을 더한 합을 구하라. 합이 클 수 있으므로 $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$으로 나눈 나머지를 출력한다.