[EER2] 直接自然溢出啥事没有
题目背景
题目描述
给定一个整数 $n$，问有多少个长度为 $n$ 的字符串，满足这个字符串是一个“程序片段”。
具体定义如下：
单个分号 `;` 是一个“语句”。
空串 ` ` 是一个“程序片段”。
如果字符串 `A` 是“程序片段”，字符串 `B` 是“语句”，则 `AB` 是“程序片段”。
如果字符串 `A` 是“程序片段”，则 `{A}` 是“语句块”。
如果字符串 `A` 是“语句块”，则 `A` 是“语句”，`[]A` 和 `[]()A` 都是“函数”。
如果字符串 `A` 是“函数”，则 `(A)` 是“函数”，`A` 和 `A()` 都是“值”。
如果字符串 `A` 是“值”，则 `(A)` 是“值”，`A;` 是“语句”。
**注意：`A` 是 `B` 并不代表 `B` 是 `A`**。
输入输出格式
输入格式
一行，一个整数 $n$。
输出格式
一行，一个整数，表示答案对 $18\,446\,744\,073\,709\,551\,616$（$2^{64}$） 取模的结果。
输入输出样例
输入样例 #1
4输出样例 #1
9输入样例 #2
7输出样例 #2
140说明
### 样例一解释
合法的“程序片段”有：`;;;;`，`;;{}`，`;{;}`，`;{};`，`{;;}`，`{;};`，`{{}}`，`{};;`，`{}{}`。
注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。
子任务 1（$20$ 分）：$n\leq 10$。
子任务 2（$20$ 分）：$n\leq 100$。
子任务 3（$20$ 分）：$n\leq 2500$。
子任务 4（$40$ 分）：没有特殊限制。
对于 $100\%$ 的数据，$0\leq n\leq 10^4$。