## Proper Bracket SequencesProblem #140 |

*This problem was brought to me by some colleague at forum - he got it at interview for position of Ruby-on-Rails
web-developer and was somewhat confused.*

You probably remember Matching Brackets task. This one is also about brackets but of a single kind - let them be round brackets.

The string of brackets is correct if the following conditions hold:

- amounts of opening and closing brackets are equal;
- for any "prefix" (i.e. substring starting from the beginning of the string) amount of opening brackets is greater or equal to amount of closing ones.

So for example:

```
(()(()(()))) - correct sequence
)()()( - not correct, substring(0, 1) contains 1 closing brackets and no opening
()(()(()) - not correct, one extra opening bracket.
```

For given `N`

you are to tell how many correct bracket strings of length `2N`

could be built.

Here is only one variant for `N=1`

:

```
()
```

Two variants for `N=2`

:

```
(()) ()()
```

Five for `N=3`

:

```
((())) (())() ()(()) (()()) ()()()
```

And so on.

**Input data** contain a single value `N`

, not exceeding `400`

.

**Answer** should contain exact (though perhaps pretty long) number of variants.

Example:

```
input data:
10
answer:
16796
```

You need to login to get test data and submit solution.