Number of Unique Binary Trees

Given a positive integer n representing the number of nodes, determine how many structurally unique binary trees can be formed using exactly those n nodes.

Input

• A single integer n satisfying $1 \le n \le 19$.

Output

• A single integer: the count of distinct binary tree shapes that can be built with n nodes.

Examples

Example 1

Input:

3

Output:

5

Explanation: With three nodes you can construct five different tree shapes: the root can have two children, a left child that itself has a left child, a left child that itself has a right child, a right child that itself has a left child, or a right child that itself has a right child.

Example 2

Input:

1

Output:

1

Explanation: A single node can only form one tree shape.

Example 3

Input:

2

Output:

2

Explanation: With two nodes the root can have either a left child or a right child, giving two distinct shapes.