ASCII Выражение
Математические выражения, встречающиеся в старых статьях и технических документах, часто печатались на пишущей машинке в несколько строк, используя шрифт с фиксированной шириной. Рассмотрим следующее математическое выражение:
Оно представлено в следующих четырех строках: 4 2(1 - —-) * - 5 + 6 2 3, где "- 5" обозначает унарный минус перед числом 5. Такое выражение из строк мы называем "ASCII-выражением".
Ваша задача — написать программу, которая распознает структуру ASCII-выражений, полученных с помощью оптического распознавания символов (OCR) из старых документов, и вычисляет их значения.
Для упрощения предположим, что ASCII-выражения построены по следующим правилам, синтаксис которых показан в Таблице 1.
Например, отрицательная дробь представлена в трех строках:
3- — 4
где самый левый дефис обозначает унарный минус. Между унарным минусом и винкулумом дроби должен быть один пробел.
Дробь представлена в четырех строках:
3 + 4 * -2————- 2- 1 - 2
где ширина ячеек делимого и делителя равна 11 и 8 соответственно. Следовательно, количество дефисов винкулума равно 2 + max(11, 8) = 13. Делитель центрируется с помощью ⌈(13−8)/2⌉ = 3 пробелов (дефисов) слева и ⌊(13−8)/2⌋ = 2 справа.
Выражение powexpr (4^2)^3 представлено в двух строках:
2 3( 4 )
где ячейка для 2 расположена на одну строку выше базовой линии ячейки для 4, а ячейка для 3 — на одну строку выше базовой линии ячейки для первичного (4^2).
Входные данные
Входные данные состоят из нескольких наборов данных, за которыми следует строка, содержащая ноль. Каждый набор данных имеет следующий формат:
nstr1str2...strn
n — положительное целое число, указывающее количество следующих строк одинаковой длины, представляющих ячейку ASCII-выражения. str_k — это k-я строка ячейки, где каждый пробел заменен точкой.
Можно предположить, что n ≤ 20 и длина строк не превышает 80.
Выходные данные
Для каждого набора данных нужно вывести одну строку, содержащую неотрицательное целое число меньше 2011. Это число представляет значение ASCII-выражения в модульной арифметике по модулю 2011. Вывод не должен содержать никаких других символов.
Обратите внимание, что powexpr x^0 определяется как 1, а x^y (y — положительное целое число) определяется как произведение x×x×...×x, где количество x равно y.
Дробь вычисляется как произведение x и обратного к y, то есть x× inv(y), по модулю 2011. Обратное к y (1 ≤ y < 2011) однозначно определяется как целое число z (1 ≤ z < 2011), которое удовлетворяет z × y ≡ 1 (mod 2011), так как 2011 является простым числом.