Counting Program Fragments

Given an integer \( n \), count the number of strings of length \( n \) that represent a valid "program fragment" according to the following rules. All formulas are given in LaTeX format.

The definitions are as follows:

• \( ; \) is a statement.
• The empty string \( \epsilon \) is a program fragment.
• If string \( A \) is a program fragment and string \( B \) is a statement, then the concatenation \( AB \) is a program fragment.
• If string \( A \) is a program fragment, then \( \{A\} \) is a statement block.
• If \( A \) is a statement block, then \( A \) is a statement, and both \( []A \) and \( []()A \) are functions.
• If \( A \) is a function, then \( (A) \) is a function, and both \( A \) and \( A() \) are values.
• If \( A \) is a value, then \( (A) \) is a value and \( A; \) is a statement.

Note: The fact that \( A \) is \( B \) does not imply that \( B \) is \( A \).

Your task is to compute the number of valid program fragments of length \( n \) using these rules. It is guaranteed that \( n \) is small enough so that a dynamic programming solution is feasible.

inputFormat

The input consists of a single integer \( n \) representing the length of the string.

outputFormat

Output a single integer, the number of valid program fragments of length \( n \).

sample

0

1