《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。 

 只有一行，其中有一个正整数 n，30%的数据满足 n≤20。 

#include
    
     #include
     
      #include
      
       #define P 1000000001using namespace std;int f[2][1<<12],n,vis[1<<12];long long ans(1);int cal(int x){  int i,j,t,a,b,pre(0),ans(0);  memset(f,0,sizeof(f));  f[1][0]=1;  for (i=0;x*(1<
       
        <=n;i++){    memset(f+(i&1),0,sizeof(f)>>1);    for (j=0,t=1;x*t*(1<
        
         <=n;j++,t*=3);    for (a=0;a<(1<
         
          >1&i)) vis[i]=1; for (int i=1;i<=n;i++) if (i%2&&i%3) ans*=cal(i),ans%=P; cout<
          
           <