《集合论与图论》这门课程有一道作业题，要求同学们求出 的所有满足以下条件的子集：若 在该子集中，则 和 不能在该子集中。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 ，如何求出 的满足上述约束条件的子集的个数（只需输出对 取模的结果），现在这个问题就交给你了。
只有一行，其中有一个正整数 。
仅包含一个正整数，表示 有多少个满足上述约束条件的子集。
4
8
【样例解释】
有 个集合满足要求，分别是 、、、、、、 和 。
【数据范围】
对于 的数据，。 对于 的数据，。
