放上我的代码，第 $2$ 个点被卡了好久：

#include<bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

const int mod = 1e9 + 1;
const int N = 1e5 + 1;
const int M = 100001;
const int K = 20;

int n, r, ans = 1;
int a[K][K], c[K], f[K][M];
bool used[N], vis[M + 2];

inline int help(int x){
  for(int i = 1; i <= 11; i = -~i){
    a[i][1] = (i == 1 ? x : a[i - 1][1] * 3);
    if(a[i][1] > n){
      r = i - 1;
      break;
    }
    used[a[i][1]] = true;
    for(int j = 2; j <= 17; j = -~j){
      a[i][j] = a[i][j - 1] * 2;
      if(a[i][j] > n){
        c[i] = j - 1;
        break;
      }
      used[a[i][j]] = true;
    }
  }
  for(int i = 1; i <= r; i = -~i){
    for(int j = 0; j <= M - 5; j = -~j){
      f[i][j] = 0;
    }
  }
  for(int i = 0; i < ( 1 << c[1] ); i = -~i){
    f[1][i] = vis[i];
  }
  for(int i = 2; i <= r; i = -~i){
    for(int j = 0; j < 1 << c[i]; j = -~j){
      if(vis[j]){
        for(int k = 0; k < 1 << c[i - 1]; k = -~k){
          if(vis[k] && !(k & j)){
            f[i][j] += f[i - 1][k];
            f[i][j] %= mod;
          }
        }
      }
    }
  }
  int sum = 0;
  for(int i = 0; i < ( 1 << c[r] ); i = -~i){
    sum += f[r][i];
    sum %= mod;
  }
  return sum;
}

signed main(){
	ios :: sync_with_stdio ( false );
	cin.tie ( 0 ), cout.tie ( 0 );
  cin >> n;
  for(int i = 0; i <= M - 5; i = -~i){
    vis[i] = !((i << 1) & i);
  }
  for(int i = 1; i <= n; i = -~i){
    if(!used[i]){
      ans *= help(i);
      ans %= mod;
    }
  }
  cout << ans;
  return 0;
}