正解:$dp$
解题报告:
考虑列一个横坐标为比值为2的等比数列,纵坐标为比值为3的等比数列的表格.发现每个数要选就等价于它的上下左右不能选.
于是就是个状压$dp$板子了$QwQ$
然后因为有些数是无关联的就不会在一个表格中($eg:1,5$.所以要建多个表格,最后乘法原理就好,$over$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i) const int N=+,mod=;
int n,as=,cnt,num[],f[][N];//说下昂QwQ,就这里这个[N]不是原本的N的意义,,,只是恰好等于N.QwQ
bool vis[N];
vector<int>V[]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void build(ri x)
{cnt=;while(x<=n){ri tmp=x;num[++cnt]=;while(tmp<=n)++num[cnt],vis[tmp]=,tmp<<=;x=1ll*x*;}}
il bool check(ri x){ri pre=;while(x){ri tmp=lowbit(x);if(tmp==(pre<<))return ;pre=tmp;x-=pre;}return ;}
il void pre(){rp(i,,cnt){V[i].clear();rp(j,,(<<num[i])-)if(check(j))V[i].push_back(j);}}
il void inc(ri &x,ri y){x+=y;if(x>=mod)x-=mod;}
il int cal()
{
pre();ri ret=;
rp(i,,cnt){ri sz=V[i].size();rp(j,,sz-)f[i][j]=(i==);}
rp(i,,cnt)
{
ri sznw=V[i].size(),szpr=V[i-].size();
rp(j,,sznw-){rp(k,,szpr-)if(!(V[i][j]&V[i-][k]))inc(f[i][j],f[i-][k]);if(i==cnt)inc(ret,f[i][j]);}
}
if(cnt==)ret=V[].size();
return ret;
} int main()
{
//freopen("3226.in","r",stdin);freopen("3226.out","w",stdout);
n=read();rp(i,,n)if(!vis[i]){build(i);as=1ll*as*cal()%mod;}printf("%d\n",as);
return ;
}