<h2>题意</h2>

定义一个集合 $S$ 是好的，当且仅当：

1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$，这里 $\oplus$ 是异或操作。
2. 集合最大值 $\leq n$

求这样的集合的个数，模 $10 ^9+7$

<h2>题解</h2>

这是个好题（至少我觉得我是想不出来）
首先一个观察是这样的集合一定是由一组线性基生成出来的，我们只需要搞出一个让线性基和集合的一一对应关系，就可以很方便的 dp 了。
我们考虑用线性基求最大异或和的时候，我们需要使用高斯消元每次选取出第一位非 $0$ 位最靠前的那一个向量，去消掉这一位上其他的 $1$，如果有的变成 $0$ 了说明能被线性组合出来不合法。观察消元后的线性基，我们可以发现存在一些列只有一个 $1$（主元列），我们对这个结果进行计数。
数位 $dp$ ：设 $f_{i,j,lim}$ 表示从高往低考虑到第 $i$ 位，已经用了 $j$ 个向量去限定，现在是否卡上界。分类讨论：

1. 不卡上界
   考虑这一位可以使用一个单独的向量限定为 $1$，也可以在已经有的向量里限定。

如果开一个单独的向量那么必须钦定目前已有的向量这一位都是 0，就是 $f_{i-1,j+1,0}$ 种方案。
如果这一位用之前的向量限定，那么每个向量这一位都可以填 $0$ 和 $1$，就有 $f_{i-1,j,0}*2^j$ 种方案。

1. 卡上界
   这里和上面唯一不同的地方就是我们需要求出限定这一位为 $0/1$ 的方案。由于最大值是所有向量异或起来，那么如果这一位有奇数个 $1$ 那么这一位就是 $1$，否则就是 $0$，方案数都是 $2^{j-1}$。但是如果之前还没有基这一位就只能是 $0$ 需要特判一下（

<h2>代码</h2>

挺好写的

/*
 * Author: RainAir
 * Time: 2019-10-08 10:02:13
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 40+5;
const int ha = 1e9 + 7;
int fMAXN[2],pw[MAXN];
// 第 i 位搞了 j 个基
int a[MAXN],len;

inline int dfs(int i,int j,int lim){
    if(!i) return 1;
    if(fi[lim] != -1) return fi[lim];
    int ans = 0;
    if(!lim){
        (ans += 1lldfs(i-1,j,0)pw[j]%ha) %= ha;
        (ans += dfs(i-1,j+1,0)) %= ha;
    }
    else{
        (ans += (1lldfs(i-1,j,!a[i])(!j ? 1 : pw[j-1])%ha))%=ha;
        if(a[i]){
            (ans += dfs(i-1,j+1,1)) %= ha;
            (ans += (1lldfs(i-1,j,1)(!j ? 0 : pw[j-1])%ha)) %= ha;
            // 前面没有基，这一位只能是 0
        }
    }
    return fi[lim] = ans;
}

int main(){
    CLR(f,-1);
    pw[0] = 1;
    FOR(i,1,MAXN-1) pw[i] = (pw[i-1]<<1)%ha;
    int x;scanf("%d",&x);
    while(x) a[++len] = x&1,x >>= 1;
    printf("%dn",dfs(len,0,1));
    return 0;
}