Count Balanced Binary Trees

You are given a non-negative integer h representing the height of a balanced binary tree. Your task is to determine the number of distinct balanced binary trees of height h.

The number of balanced binary trees can be computed using dynamic programming with the recurrence relation in LaTeX format as follows:

$$dp[i] = dp[i-1]^2 + 2\times dp[i-1]\times dp[i-2],$$

with the base cases:

$$dp[0] = 1 \quad\text{and}\quad dp[1] = 1.$$

Your solution should read the integer h from standard input and output the computed number on standard output.

inputFormat

Standard Input (stdin): A single non-negative integer h representing the height of the balanced binary tree.

outputFormat

Standard Output (stdout): A single integer, the number of balanced binary trees of height h.

0

1