eolymp
bolt
Try our new interface for solving problems
Problems

Bracket Maze

Bracket Maze

Time limit 1 second
Memory limit 64 MiB

We are given a maze which is a cube of n * n * n cells. We start at (1,1,1) and we move to (n,n,n), in each move visiting one of the three adjacents cells in the positive x, y or z directions. Each cell of the maze contains either a '(', ')' or '.'. A path is the sequence of cells visited during the journey. We intend to find the number of such paths that produce a valid parenthesized expression.

Periods can occur freely in an expression, and must be ignored while checking if an expression is properly paranthesized or not. A paranthesized expression is said to be valid only if it adheres to the following grammar (quotes for clarity):

::= empty-string | "("")" | "." |

e.g., "(())", "....", ".()." and "().(.)" are valid parathesized expressions.

The maze is given in a string which represents the cube encoded in the following manner. The characters of maze correspond to the following cube coordinates, in order:

(1,1,1), (1,1,2), ..., (1,1,n), (1,2,1), (1,2,2), ..., (1,n,n), (2,1,1), ..., (n,n,n)

Input data

Each line contains the positive integer n (1n13) and the string maze that consists of exactly n^3 characters.

Output data

For each test case print in a separate line the number of paths from (1, 1, 1) to (n, n, n) that produce a valid parenthesized expression. If there are more than 1,000,000,000 paths, print -1 instead.

Examples

Input example #1
2 ()()()()
3 ...........................
2 )()()()(
Output example #1
2
90
0