941. All Possible Full Binary Trees (Count)

A full binary tree is one where every node has either zero or two children. Given an integer n, return the number of structurally distinct full binary trees with exactly n nodes, modulo 1,000,000,007. If no such tree exists (n even), return 0. The input is the integer n.

Input: The integer n.

Output: Integer — the count of full binary trees mod 1e9+7.

Examples

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

Input: 3
Output: 1
Explanation: Only one shape.

Input: 4
Output: 0
Explanation: No full binary tree with 4 nodes.

Constraints

• 1<=n<=250

Asked by