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