Count the BST shapes

Problem

How many different binary search trees can be built from n different keys? Two trees are different if their shapes are different. Print the count.

Example 1

Input

Output

The shapes for 1, 2, 3 are five.

Example 2

Input

Output

Try the problem first. Open one hint at a time.

Hint 1

Pick the root key. If it is the ith smallest, the left subtree uses i - 1 keys and the right subtree uses n - i keys.

Hint 2

The two sides are independent, so multiply their counts and add over all roots.

Write your Python code, run it on the examples and submit it to hidden tests.