Suppose `T_n` is a perfect binary tree of height `n`, that is each node has exactly two children except that nodes at top level have no children. `T_3` and `T_4` are drawn in the following figure .
An apple tree of height `n` is a prefect binary tree of height `n` where apples may grow at any node except the root and no apples are grown at adjacent nodes. For example, the following figure shows an apple tree of height `3` and an apple tree of height `4`. Nodes with apples are in red.
`a(n)` is the number of distinct apple trees of height `n`.
For example, `a(1)=1`, `a(2)=4`, `a(3)=25`.
Find `a(n)`.