795. All Possible Full Binary Trees — Count

A FULL binary tree is a tree where every node has exactly 0 or 2 children. Given an integer n, return the number of structurally distinct full binary trees with exactly n nodes. If n is even, the answer is 0 (full binary trees always have an odd number of nodes). Use a recursive formulation: FBT(n) = sum over odd left sizes l in [1, n-2] of FBT(l) * FBT(n-1-l).

Input: A single positive integer n.

Output: Return an integer count.

Examples

Input: 7
Output: 5
Explanation: Five structurally distinct full binary trees with 7 nodes.

Input: 3
Output: 1
Explanation: Only one FBT with 3 nodes (root + 2 leaves).

Input: 4
Output: 0
Explanation: Even n has no full binary trees.

Constraints

• 1 <= n <= 72

Asked by