这个菜狗考场上找了2h的假规律，现在只会$n = 2^k - 1$的做法了（虽然正解是线性基，但还是想问问找规律的做法）

int m = 0;
for (; (1 << m) < n; ++m);
for (int i = 0, s = 1, j = 1; i * 2 <= m; ++i) {
  s = (1ll * s * ksm((j - 1 + Mod) % Mod, Mod - 2)) % Mod;
  if (!s) s = 1;
  ans = (1ll * ans + s) % Mod;
  if (i * 2 < m) ans = (1ll * ans + s) % Mod;
  j = (2ll * j) % Mod;
  s = (1ll * s * ((ksm(2, m - i) - 1 + Mod) % Mod)) % Mod;
}
cout << ans;

($n = 2^k - 1$做法的部分代码)

(一些奇怪的规律，可能有帮助)