Description

Given an integer $n$, ask how many strings of length $n$ satisfy that the string is a “program fragment”.

The exact definitions are as follows:

A single semicolon ; is a “statement”.

The empty string is a “program fragment”.

If string A is a “program fragment” and string B is a “statement”, then AB is a “program fragment”.

If string A is a “program fragment”, then {A} is a “statement block”.

If string A is a “statement block”, then A is a “statement”, and []A and []()A are both “functions”.

If string A is a “function”, then (A) is a “function”, and A and A() are both “values”.

If string A is a “value”, then (A) is a “value”, and A; is a “statement”.

Note: A being B does not mean that B is A..

Input Format

One line containing one integer $n$.

Output Format

One line containing one integer, representing the result of the answer modulo $18\,446\,744\,073\,709\,551\,616$ ($2^{64}$).

4

9

7

140

Hint

Explanation for Sample 1

Valid “program fragments” include: ;;;;, ;;{}, ;{;}, ;{};, {;;}, {;};, {{}}, {};;, {}{}.

Note: This problem uses bundled tests. You will get the score for a subtask only after you pass all test points in that subtask.

Subtask 1 ($20$ points): $n \leq 10$.

Subtask 2 ($20$ points): $n \leq 100$.

Subtask 3 ($20$ points): $n \leq 2500$.

Subtask 4 ($40$ points): no special constraints.

For $100\%$ of the testdata, $0 \leq n \leq 10^4$.

Translated by ChatGPT 5