前言：
废掉了
T1.线性代数
考场时想到了线性基，但是思路仅从基底入手，没想到如何维护这个基的最大值小于 \(n\)。
题解：
容易想到线性代数，相当于就是求任意元素小于 \(n\) 的一维线性空间个数。
由于一个线性空间可能对应多个基，我们不妨以这个线性空间的最大值作为标识。
容易知道，每个基底在二进制表示下的最高位不同，所以按照二进制标识下最高位进行枚举。
\(dp[i][j][1/0]\) 表示考虑二进制表示下前 \(i\) 位，基大小为 \(j\)，此时线性空间最大值是/否等于 \(n\) 在二进制表示下的前 \(i\) 位。
转移考虑是否要添加一个二进制标识下最高位为 \(i\) 的基底，或者前 \(j - 1\) 个第 \(i\) 位可以随便选，然后根据前 \(j - 1\) 个的结果选择第 \(j\) 个的第 \(i\) 为零或者 \(1\)（你不必知道前 \(j - 1\) 个异或出来的最大值第 \(i\) 位的数值，你只需要知道你的第 \(j\) 个数的第 \(i\) 位不自由即可，考试时我就卡在这里）。
参考代码
// ubsan: undefined
// accoders
#include <set>
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <random>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define db double
#define LL long long
//#define int long long
#define PII pair <int, int>
#define ULL unsigned long long
#define MP(x,y) make_pair (x, y)
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)
template <typename T>
void read (T &x) {
x = 0; T f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
x *= f;
}
template <typename T, typename... Args>
void read (T &x, Args&... Arg) {
read (x), read (Arg...);
}
const int MaxPrint = 1000;
int Poi_For_Print, Tmp_For_Print[MaxPrint + 5];
template <typename T>
void write (T x) {
if (x == 0) {
putchar ('0');
return;
}
bool flag = (x < 0 ? 1 : 0);
x = (x < 0 ? -x : x);
while (x) Tmp_For_Print[++Poi_For_Print] = x % 10, x /= 10;
if (flag) putchar ('-');
while (Poi_For_Print) putchar (Tmp_For_Print[Poi_For_Print--] + '0');
}
template <typename T, typename... Args>
void write (T x, Args... Arg) {
write (x); putchar (' '); write (Arg...);
}
template <typename T, typename... Args>
void print (T x, char ch) {
write (x); putchar (ch);
}
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
const int Maxk = 30;
const LL Mod = 1e9 + 7;
int n;
int tp, st[Maxk + 5];
LL f[Maxk + 5][Maxk + 5];
LL dfs (int step, int cnt, int Limit) {
if (step == -1) {
return 1;
}
if (!Limit && f[step][cnt]) return f[step][cnt];
int up = (Limit ? st[step] : 1);
//在填第 cnt 个主元的第 step 位
LL res = 0;
rep (i, 0, up) {
if (cnt == 0 && i == 1) continue;
//根据前 cnt - 1 个主元异或结果的第 step 位决定第 cnt 个主元的第 step 位填什么
res += dfs (step - 1, cnt, Limit & (i == up)) * (cnt == 0 ? 1 : (1 << (cnt - 1))) % Mod;
res %= Mod;
}
//准备新加入主元，最高位为 step
if (up)
res += dfs (step - 1, cnt + 1, Limit), res %= Mod;
if (!Limit) f[step][cnt] = res;
return res;
}
signed main () {
// freopen ("C:\\Users\\HP\\Desktop\\lihan\\1.in", "r", stdin);
// freopen ("C:\\Users\\HP\\Desktop\\lihan\\1.out", "w", stdout);
freopen ("algebra.in", "r", stdin);
freopen ("algebra.out", "w", stdout);
read (n);
int tmp = n;
while (tmp)
st[tp++] = tmp & 1, tmp >>= 1;
tp--;
write (dfs (tp, 0, 1));
return 0;
}