P6103 [EER2] Direct Natural Overflow, Nothing Happens


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`.**.

One line containing one integer $n$.

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

### 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