Compute the nth Motzkin Number

Your task is to compute the nth Motzkin number. The Motzkin number represents the number of ways to draw non-intersecting chords among n points on a circle.

It can be defined as follows:

\(M(0)=1,\ M(1)=1\)

For \(n > 1\), \[ M(n)=M(n-1)+\sum_{i=0}^{n-2} M(i) \cdot M(n-2-i) \]

Given an integer \(n\), calculate \(M(n)\) and output the result.

inputFormat

A single integer \(n\) (with \(0 \le n \le 30\)) provided via standard input.

outputFormat

Output a single integer which is the nth Motzkin number, printed to standard output.

0

1