Symmetry Trees

You are given an integer n representing the number of nodes. Your task is to compute the number of distinct Symmetry Trees that can be constructed with exactly n nodes. A symmetry tree is defined such that it has a central root node and two identical subtrees. The trees are counted modulo \(10^9 + 7\).

The approach uses dynamic programming. Let \(dp[i]\) denote the number of symmetry trees we can form with exactly \(i\) nodes. We initialize \(dp[0] = 1\) and \(dp[2] = 1\). For any even number \(n \geq 4\), the recurrence is given by:

[ dp[n] = \sum_{\text{left}=0}^{n-2, \text{step }2} ; dp[\text{left}] \times dp[n-2-\text{left}] \quad \text{(mod }10^9+7\text{)} ]

If \(n\) is odd, then it is impossible to form a symmetry tree, and the answer is \(0\). Your solution should take the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of a single integer n on a single line, representing the total number of nodes.

Constraints:

• \(0 \leq n \leq 10^5\)

outputFormat

Output the number of distinct symmetry trees that can be constructed with n nodes, computed modulo \(10^9+7\).

2

1