背景

题目描述

给定一个整数 $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}$） 取模的结果。

4

9

7

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$。