eolymp
bolt
Try our new interface for solving problems
Problems

ASCII Expression

ASCII Expression

Time limit 1 second
Memory limit 64 MiB

Mathematical expressions appearing in old papers and old technical articles are printed with typewriter in several lines, where a fixed-width or monospaced font is required to print characters (digits, symbols and spaces). Let us consider the following mathematical expression.

It is printed in the following four lines: 4 2(1 - —-) * - 5 + 6 2 3where "- 5" indicates unary minus followed by 5. We call such an expression of lines "ASCII expression".

For helping those who want to evaluate ASCII expressions obtained through optical character recognition (OCR) from old papers, your job is to write a program that recognizes the structure of ASCII expressions and computes their values.

For the sake of simplicity, you may assume that ASCII expressions are constructed by the following rules. Its syntax is shown in Table 1.

For example, the negative fraction is represented in three lines:

3- — 4

where the left-most hyphen means a unary minus operator. One space character is required between the unary minus and the vinculum of the fraction.

The fraction is represented in four lines:

3 + 4 * -2————- 2- 1 - 2

where the widths of the cells of the dividend and divisor are 11 and 8 respectively. Hence the number of hyphens of the vinculum is 2 + max(11, 8) = 13. The divisor is centered by ⌈(13−8)/2⌉ = 3 space characters (hyphens) to the left and ⌊(13−8)/2⌋ = 2 to the right.

The powexpr (4^2)^3 is represented in two lines:

2 3( 4 )

where the cell for 2 is placed one line above the base-line of the cell for 4, and the cell for 3 is placed one line above the base-line of the cell for a primary (4^2).

Input data

The input consists of multiple datasets, followed by a line containing a zero. Each dataset has the following format.

nstr1str2...strn

n is a positive integer, which indicates the number of the following lines with the same length that represent the cell of an ASCII expression. str_k is the k-th line of the cell where each space character is replaced with a period.

You may assume that n20 and that the length of the lines is no more than 80.

Output data

For each dataset, one line containing a non-negative integer less than 2011 should be output. The integer indicates the value of the ASCII expression in modular arithmetic under modulo 2011. The output should not contain any other characters.

There is no fraction with the divisor that is equal to zero or a multiple of 2011.

Note that powexpr x^0 is defined as 1, and x^y (y is a positive integer) is defined as the product x×x×...×x where the number of x's is equal to y.

A fractionis computed as the multiplication of x and the inverse of y, i.e., x× inv(y), under y modulo 2011. The inverse of y (1y < 2011) is uniquely defined as the integer z (1z < 2011) that satisfies z × y ≡ 1 (mod 2011), since 2011 is a prime number.

Examples

Input example #1
4
........4...2..........
(.1.-.----.)..*.-.5.+.6
........2..............
.......3...............
3
...3.
-.---
...4.
4
.3.+.4.*.-.2.
-------------
..........2..
...-.1.-.2...
2
...2..3
(.4..).
1
2.+.3.*.5.-.7.+.9
1
(.2.+.3.).*.(.5.-.7.).+.9
3
.2....3.
4..+.---
......5.
3
.2......-.-.3.
4..-.-.-------
..........5...
9
............1............
-------------------------
..............1..........
.1.+.-------------------.
................1........
......1.+.-------------..
..................1......
...........1.+.-------...
................1.+.2....
15
.................2......
................---.....
.......2.........5....3.
.(.---------.+.-----.)..
.....7...........3......
....---.+.1.............
.....4..................
------------------------
.......2................
......---...............
.......5.......2....2...
...(.-----.+.-----.)....
.......3.......3........
..............---.......
...............4........
2
.0....2....
3..+.4..*.5
20
............2..........................
...
Output example #1
501n502n1n74n19n2010n821n821n1646n148n81n1933n
Source Asia Regional Fukuoka, Japan, 2011-11-13