Evaluation

Time limit2sMemory limit512 MB

Summary

Evaluate an expression drawn as 2D ASCII art modulo 10^9+7, where the art encodes numbers, parentheses, fourth roots, operators, and fractions.

Level: Hard8 of 10
Topics: Implementation, Recursion, Number theory
Solved: No attempts yet

Problem

Two pictures are defined first.

$S(r,c)$ is a picture of width $c$ and height $r$ made only of spaces.
$V_h$ is a picture of width 1 and height $h$ made only of | characters.

An expression $E$ is one of the following five forms.

Number. $E$ has the form below, and $\mathrm{eval}(E) = n \bmod p$ . It is given that $n \ge 0$ . Here $h_1, h_2 \ge 0$ , and $E$ has width $L$ and height $h_1+h_2+1$ .


$S(h_1,L)$
$n$ (length $L$ )
$S(h_2,L)$

Parentheses. $\mathrm{eval}(E) = \mathrm{eval}(E')$ .

If the height of $E'$ is 1, $E$ has the form below, with width $L+2$ and height 1.

`(`	E' (width $L$ )	`)`

If the height of $E'$ is $H \ge 2$ , $E$ has the form below, with width $L+2$ and height $H$ .

| / | E' (width $L$ ) | \ | | $V_{H-2}$ | | $V_{H-2}$ | | \ | | / |

Root. $E$ has the form below, and $\mathrm{eval}(E) = \min\{0 \le x < p : x^4 = \mathrm{eval}(E')^2 \bmod p\}$ . $E$ has width $L+3$ and height $H+1$ .


$S(H,2)$		`+`	string of `-` of length $L$
		$V_{H-1}$	E' (width $L$ , height $H$ )
`/`	`\`	`\|`

Operation. $E$ has the form below, where op is one of +, -, *, /. $\mathrm{eval}(E) = (\mathrm{eval}(E_1) \mathrm{op} \mathrm{eval}(E_2)) \bmod p$ . Here $\mathrm{eval}(E_1) / 0 = 19981204$ . $E$ has width $L_1+L_2+3$ and height $H$ .

E1 (width $L_1$ , height $H$ )	$S(H,1)$	$S(\lfloor H/2 \rfloor,1)$	$S(H,1)$	E2 (width $L_2$ , height $H$ )
		op
		$S(\lfloor (H-1)/2 \rfloor,1)$

Fraction. $E$ has the form below, and $\mathrm{eval}(E) = (\mathrm{eval}(E_1) / \mathrm{eval}(E_2)) \bmod p$ . $E$ has width $L+2$ and height $H_1+H_2+1$ .

$S(H_1,1)$	E1 (width $L$ , height $H_1$ )	$S(H_1,1)$
string of `-` of length $L+2$
$S(H_2,1)$	E2 (width $L$ , height $H_2$ )	$S(H_2,1)$

The input is given so that no expression has more than one parse tree under these rules. In all of the above, $p = 10^9 + 7$ is prime.

Input

The first line has the number of rows $R$ and the number of columns $C$ . Each of the next $R$ lines has $C$ characters, and together they give the expression $E_0$ . The width of $E_0$ is $C$ and its height is $R$ .

Output

Print eval( $E_0$ ).

Examples1

Example 1

Input

6 10
/   +--- \
|   | 6  |
|   |--- |
| /\| 3  |
|--------|
\ 12 - 9 /

Expected output

353237869