题意：
给定非负整数 \(n\)，定义一个自然数集合 \(S\) 是好的，当且仅当 \(\forall x\in S,x\le n\) 且 \(\forall x,y\in S,x\oplus y\in S\)，其中 \(\oplus\) 表示按位异或。
问好集合 \(S\) 的个数，对 \(10^9+7\) 取模。
约定：
- \(\oplus\) 表示按位异或。
- \(x[i]\) 表示二进制自然数 \(x\) 从低到高第 \(i\) 位，\(i\) 从 \(0\) 起。显然 \(x[i]\in\{0,1\}\)。
- \(h(x)=\left\lfloor\log_2x\right\rfloor\)，表示使得 \(x[k]=1\) 的最大的 \(k\)，\(h(0)\) 未定义。
- \(\gg\) 表示右移运算。
将每个自然数看做一个 \(t\) 维异或向量（\(t=h(n)\)），那么一个满足 \(\forall x,y\in S,x\oplus y\in S\) 的 \(S\) 就是一个线性空间，可以用一个线性基表示。
但是每个线性空间可能对应多个线性基，于是考虑对每一个线性空间选一个特殊的线性基 \(B\)，它是由对这个线性空间的每个元素高斯消元得到的，它满足性质：\(\forall i\in[0,t-1]\)，如果 \(\exists x\in B,h(x)=i\)，那么 \(\forall y\in B\vee y\neq x,y[i]=0\)，因为如果 \(\exists y\in B, y\neq x,y[i]=1\)，我们可以令 \(y\leftarrow y\oplus x\) 使 \(y[i]=0\) 并不破坏线性基的性质。如果 \(\exists x\in B,h(x)=i\)，那么我们称第 \(i\) 位是“有效”的。这样的线性基还有一个性质，它能组成的最大数就是其中每个数的异或和，记这个数为 \(m\)。
考虑从高位到低位 DP，因为低位对 \(m\) 的大小的影响比高位的影响更小。
设 \(f(i,j)\) 表示处理到第 \(i\) 位，线性基中有 \(j\) 个数（有 \(j\) 个有效位），总共的方案数。然后我们发现这样无法处理 \(m\le n\) 的限制，于是考虑再添加一个状态 \(k\)，如果目前为止的 \(m\) 是否满足 \(m\gg i=n\gg i\)，则 \(k=1\)，如果 \(m\gg i<n\gg i\) 则 \(k=0\)，\(m\gg i>n\gg i\) 的情况没有贡献，不用考虑。
初始状态显然 \(f(t-1,0,0)=f(t-1,1,1)=1\)。
当处理到第 \(i\) 位时，有两种决策：令第 \(i\) 位有效或无效。当 \(j=0\) 时，\(B=\varnothing,m=0\)，所以\(f(i,0,0)=1,f(i,0,1)=0\)。接下来分类讨论 \(k\) 和 \(n[i]\)。
- \(k=0,n[i]=0\)：如果高位的 \(m\) 已经小于 \(n\) 了（\(k=0\)），那么这位是否有效都没关系，有效的贡献为 \(f(i+1,j-1,0)\)，如果无效则其他元素这一位可以随便填，贡献为 \(f(i+1,j,0)\times2^j\)。如果高位 \(m=n\) 卡死（\(k=1\)），则不能转移到这个状态。
- \(k=0,n[i]=1\)：有效的贡献还是 \(f(i+1,j-1,0)\)。如果无效，可以和上一中一样由 \(k=0\) 的状态转移，贡献为 \(f(i+1,j,0)\times2^j\)，还可以由 \(k=1\) 的状态转移，这时要保证这一位的异或和为 \(0\)，也就是恰好填了偶数个 \(1\)，随便填的方案是 \(2^j\)，奇偶对称，偶数的方案就是 \(2^{j-1}\)，所以这部分的贡献是 \(f(i+1,j,1)\times2^{j-1}\)。
- \(k=1,n[i]=0\)：必须卡死，所以只能由 \(k=1\) 的状态转移来。又因为 \(n[i]=0\)，所以这一位必须无效，且只能有偶数个 \(1\)，所以 \(f(i,j,1)=f(i+1,j,1)\times2^{j-1}\)。
- \(k=1,n[i]=1\)：同理只能由 \(k=1\) 的状态转移来。有效的贡献是 \(f(i+1,j-1,1)\)，无效要使这一位有奇数个 \(1\)，因为奇偶对称所以还是 \(2^{j-1}\) 种填法，因此贡献为 \(f(i+1,j,1)\times2^{j-1}\)。
最后的答案就是 \(\sum\limits_{i=0}^{t}f(0,i,0)+f(0,i,1)\)。
时间复杂度 \(O(\log^2n)\)。
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
#define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 31, mod = 1e9 + 7;
int n, a[N], f[N][N][2], pw[N];
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n;
if(n == 0) cout << "1\n", exit(0);
pw[0] = 1;
rep(i, 1, 30) pw[i] = pw[i - 1] * 2 % mod;
int t = 0;
for(; n; ++t, n >>= 1)
a[t] = n & 1;
f[t - 1][0][0] = 1;
f[t - 1][1][1] = 1;
per(i, t - 2, 0) {
f[i][0][0] = 1;
rep(j, 1, t - i) {
f[i][j][0] = (f[i + 1][j - 1][0] + f[i + 1][j][0] * pw[j]) % mod;
if(a[i]) (f[i][j][0] += f[i + 1][j][1] * pw[j - 1]) %= mod;
if(a[i]) f[i][j][1] = (f[i + 1][j - 1][1] + f[i + 1][j][1] * pw[j - 1]) % mod;
else f[i][j][1] = (f[i + 1][j][1] * pw[j - 1]) % mod;
}
}
int ans = 0;
rep(i, 0, t) (ans += f[0][i][0] + f[0][i][1]) %= mod;
cout << ans << endl;
return 0;
}