Description

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

Input

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

Output

仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件 的子集。

Sample Input

4

Sample Output

8

【样例解释】

有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。

Solution

考虑构造这样一个矩阵

\[ \begin{bmatrix} x & 3x & 9x & 27x & \cdots & \\ \\ 2x & 6x & 18x & 54x & \cdots & \\ \\ 4x & 12x & 36x & 108x & \cdots & \\ \\ 8x & 24x & 72x & 216x & \cdots & \\ \\ \vdots & \vdots & \vdots & \vdots & \ddots &\\ \end{bmatrix} \]

那么对于一个数 \(x\) ，与它有冲突关系的数就都选出来了，我们只要在矩阵上选数，并且相邻位置不能选到就可以了

这一步就是个状压dp模板题

对于不在同一矩阵的每一种 \(x\) ，都构造一个矩阵，计算答案。这些矩阵之间互不干扰，所以直接乘起来就好了

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=100000+10,Mod=1e9+1;int n,G[20],cnt,p[MAXN],vis[MAXN];ll f[20][2000],ans;template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline ll qexp(ll a,ll b){ ll res=1; while(b) { if(b&1)res=res*a%Mod; a=a*a%Mod; b>>=1; } return res;}inline bool check(int st){ return (st&(st<<1))||(st&(st>>1));}inline ll solve(ll x){ memset(G,0,sizeof(G)); int w=0,h=0; while(x*qexp(2,w)<=n)++w; while(x*qexp(3,h)<=n)++h; for(register int i=1;i<=w;++i) for(register int j=1;j<=h;++j) if(qexp(2,i-1)*qexp(3,j-1)*x<=n)vis[qexp(2,i-1)*qexp(3,j-1)*x]=1,G[i]|=(1<