Proper Bracket Sequences

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.

Problem Statement

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