Catalan Numbers

With 3 pairs of brackets you can write 5 balanced strings: ((())), (()()), (())(), ()(()) and ()()(). The number of balanced strings with n pairs is the nth Catalan number. The same numbers count the ways to cut a polygon into triangles, mountain ranges drawn with up and down strokes, and much more.

Write catalan(n) that returns the nth Catalan number. Counting starts at catalan(0) = 1: the empty string is the one balanced string with no brackets.

Examples

catalan(3)     # returns 5
catalan(0)     # returns 1
catalan(5)     # returns 42

Constraints

• 0 <= n <= 500
• The numbers grow fast (catalan(500) has 297 digits); return the exact integer.