### Problem Statement

We are given a maze which is a cube of NxNxN 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):
```      <expr> ::= empty-string | "("<expr>")" | <expr>"." | <expr><expr>
```
e.g., "(())", "....", ".()." and "().(.)" are valid parathesized expressions.

The maze is given in a String[] which, when concantenated, 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)
```

Given the String[] maze return an int representing the number of possible paths forming valid parenthesized expressions. If there are more than 1,000,000,000 paths, return -1 instead.

### Definition

 Class: BracketMaze Method: properPaths Parameters: String[], int Returns: int Method signature: int properPaths(String[] maze, int N) (be sure your method is public)

### Constraints

-maze will contain between 1 and 50 elements, inclusive.
-Each element of maze will contain between 1 and 50 characters, inclusive.
-The maze when concatenated will contain exactly N^3 characters.
-Each character in maze will be '(', ')', or '.'.
-N will be between 1 and 13, inclusive.

### Examples

0)

 `{"()()()()"}` `2`
`Returns: 2`
 There are two paths in this 2x2x2 cube. From the 3 possible moves in the beginning, you cannot go right directly which completes a "()" but all it's neighbours are ')', hence lead to an invalid expression. The other two possible moves lead to unique valid paths.
1)

 `{")()()()("}` `2`
`Returns: 0`
2)

 `{ "..........................." }` `3`
`Returns: 90`
3)

 `{"..(....)"}` `2`
`Returns: 2`
4)

 `{ "(.........................)"}` `3`
`Returns: 90`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6490

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10058&pm=6490

myprasanna

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming, String Manipulation