Counting Program Fragments

Given a positive integer n, count the number of strings of length n that are valid "program fragments". A string is a program fragment if it can be derived using the following grammar rules:

• Rule 1: A single semicolon ; is a statement.
• Rule 2: The empty string is a program fragment.
• Rule 3: If A is a program fragment and B is a statement then the concatenation AB is a program fragment.
• Rule 4: If A is a program fragment then {A} is a statement block.
• Rule 5: If A is a statement block then:
  • A is a statement.
  • []A and []()A are functions.
• Rule 6: If A is a function then (A) is also a function.
• Rule 7: If A is a function then both A and A() are values.
• Rule 8: If A is a value then both (A) (a value) and A; (a statement) are allowed.

Note: When we write "A is B", it does not imply that B can be substituted by A.

The formulas below show the productions in LaTeX format:

\(P \to \varepsilon \;|\; P \cdot S\)     (Program fragment)

\(S \to \; ; \;|\; B \;|\; V\; ;\)     (Statement)

\(B \to \{P\}\)     (Statement Block)

\(F \to \; []\,B \;|\; []()\,B \;|\; (F)\)     (Function)

\(V \to F \;|\; F() \;|\; (V)\)     (Value)

Your task is to count the number of strings of length n that are valid program fragments.

inputFormat

The input consists of a single positive integer n (where n represents the length of the string).

outputFormat

Output a single integer that is the number of valid strings of length n that form a program fragment.

sample

1

1