要求选出集合 \(S\) 满足如果 \(x\) 选择了，\(2x\) 和 \(3x\) 都不能选择。
求 \(\{1,2,\dots,n\}\) 的符合要求的子集数量。
\(n\le 10^5\)。
发现对所有除去 \(2,3\) 因子后不同的数，他们之间没有关联，完全可以分开处理。
那么设除去 \(2,3\) 因子后剩下的数为 \(x\)，则如果将所有数写成如下表格状，则我们的条件就转化为了选择矩阵的一个子集，使得相邻的数不能同时选择。
x 3x 9x 27x ...
2x 6x 12x ...
4x 12x 36x ...
8x 24x ...
发现一行的数的个数不会超过 \(\log_3 n\)，大约为 \(12\)，所以状压即可。
#define Maxn 100005
#define Maxlogn 25
#define Maxsta3 5005
#define mod 1000000001
int n,N,ans=1,All;
int dp[Maxlogn][Maxsta3],lim[Maxn],init[Maxn];
bool vis[Maxn];
inline int solve(int x)
{
N=0; int ret=0;
for(int tx2=x,tn=1;tx2<=n;tx2*=2,tn++,N++)
for(int tx3=tx2,tm=1;tx3<=n;tx3*=3,tm++)
vis[tx3]=true,lim[tn]=1<<tm;
for(int s=0;s<lim[1];s++) dp[1][s]=init[s];
for(int i=2;i<=N;i++) for(int s=0;s<lim[i];s++) if(init[s])
{
dp[i][s]=0;
for(int t=0;t<lim[i-1];t++) if(!(s&t)) dp[i][s]=(dp[i][s]+dp[i-1][t])%mod;
}
for(int s=0;s<lim[N];s++) if(init[s]) ret=(ret+dp[N][s])%mod;
return ret;
}
int main()
{
n=rd(),All=5000;
for(int i=0;i<=All;i++) init[i]=((i<<1)&i)?0:1;
for(int i=1;i<=n;i++) if(!vis[i]) ans=1ll*ans*solve(i)%mod;
printf("%d\n",ans);
return 0;
}