Скобочный лабиринт
Имеется куб размером n * n * n. Начиная движение из ячейки (1, 1, 1), необходимо прийти в (n, n, n). Из каждой ячейки можно двигаться в соседнюю по направлению возрастания x, y или z координаты. Каждая ячейка куба содержит один из символов: ‘(‘, ‘)’ или ‘.’. Путем будем называть последовательность ячеек, посещаемых при движении. Необходимо найти количество путей из (1, 1, 1) в (n, n, n), которые описывают правильную скобочную структуру.
Правильной скобочной структурой называется выражение, порождающееся грамматикой:
::= empty-string | "("")" | "." |
Выражение может содержать произвольное количество точек, которые не учитываются при определении его правильности. Например, строки "(())", "....", ".()." и "().(.)" являются правильными скобочными структурами.
Символы строки maze соответствуют координатам ячеек куба следующим образом:
(1, 1, 1), (1, 1, 2), ..., (1, 1, n), (1, 2, 1), (1, 2, 2), ...,
(1, n, n), (2, 1, 1), ..., (n, n, n)
Входные данные
Каждая строка содержит натуральное число n (1 ≤ n ≤ 13) и строку maze, которая состоит в точности из n^3 символов.
Выходные данные
Для каждого теста в отдельной строке вывести количество путей из (1, 1, 1) в (n, n, n), которые описывают правильную скобочную структуру. Если путей больше 1,000,000,000, то выведите -1.