Bracket Maze#1557
We are given a cube with dimensions n \times n \times n. Starting from cell (1, 1, 1), your task is to reach cell (n, n, n). From each cell, you may move to an adjacent cell in the increasing , , or direction. Each cell contains one of the following symbols: **'('**, **')'** or **'.'**. A path is defined as the sequence of cells visited along the way. You are to find the number of paths from (1, 1, 1) to (n, n, n) that correspond to a valid parenthesis structure.
A valid parenthesis structure is an expression generated by the following grammar:
An expression can contain any number of periods, which are ignored when determining validity. For example, **"(())"**, **"...."**, **".()."** and **"().(.)"** are valid parenthesis structures.
The characters of the string correspond to the cube cells in this order:
(1, 1, 1), (1, 1, 2), \ldots, (1, 1, n), (1, 2, 1), (1, 2, 2), \ldots, (1, n, n), (2, 1, 1), \ldots, (n, n, n)
Each line contains a positive integer (1 \leq n \leq 13) and the string consisting of exactly n^3 characters.
For each test, print in a separate line the number of paths from (1, 1, 1) to (n, n, n) that correspond to a valid parenthesis structure. If the number of such paths exceeds 1,\!000,\!000,\!000, print **-1** instead.
Example 1