首先发现全是1的序列出来的答案是卡特兰数.
所以考虑拆贡献,全是0的数列答案肯定是0,然后让每一项分别是1,重新计算这个矩阵,打表得到这个矩阵:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
350 1 0 0 0 0 0 0
0 1 1 1 1 1 1 1
0 0 1 2 3 4 5 6
0 0 0 2 5 9 14 20
0 0 0 0 5 14 28 48
0 0 0 0 0 14 42 90
0 0 0 0 0 0 42 132
0 0 0 0 0 0 0 132
0 0 1 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 2 3 4 5 6
0 0 0 2 5 9 14 20
0 0 0 0 5 14 28 48
0 0 0 0 0 14 42 90
0 0 0 0 0 0 42 132
0 0 0 0 0 0 0 132
0 0 0 1 0 0 0 0
0 0 0 1 1 1 1 1
0 0 0 1 2 3 4 5
0 0 0 1 3 6 10 15
0 0 0 0 3 9 19 34
0 0 0 0 0 9 28 62
0 0 0 0 0 0 28 90
0 0 0 0 0 0 0 90
0 0 0 0 1 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 2 3 4
0 0 0 0 1 3 6 10
0 0 0 0 1 4 10 20
0 0 0 0 0 4 14 34
0 0 0 0 0 0 14 48
0 0 0 0 0 0 0 48
右下角的数字代表当前数字为1对答案的贡献.
所有的数字组成一个数列,oeis一下知道公式之后就可以nlogn计算了.
exp:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace fastio{
const int bufl=1<<20;
const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
struct IN{
FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
IN& operator>>(char &a){a=getChar();while(a<=32)a=getChar();return *this;}
IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
IN& operator>>(string &a){a.clear();char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
IN& operator>>(int &a){getInt(a);return *this;}
IN& operator>>(long long &a){getInt(a);return *this;}
IN& operator>>(__int128 &a){getInt(a);return *this;}
IN& operator>>(float &a){getDouble(a);return *this;}
IN& operator>>(double &a){getDouble(a);return *this;}
IN& operator>>(long double &a){getDouble(a);return *this;}
};
struct OUT{
FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
OUT(){IT=stdout,Eps=6,Acc=0.5;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=0.5;}
inline void ChangEps(int x=6){Eps=x;}
inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
inline void putChar(int a){*os++=a;if(os==ot)flush();}
template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 ff=(a-(__int128)a)*base2[Eps+2],gg=0;ff+=50;while(ff>0){ff/=10;gg++;}__int128 b=a;if(gg==Eps+3){putInt(b+1);}else{putInt(b);}a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
OUT& operator<<(char a){putChar(a);return *this;}
OUT& operator<<(const char *a){while(*a)putChar(*a++);return *this;}
OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
OUT& operator<<(int a){putInt(a);return *this;}
OUT& operator<<(long long a){putInt(a);return *this;}
OUT& operator<<(__int128 a){putInt(a);return *this;}
OUT& operator<<(unsigned int a){putInt(a);return *this;}
OUT& operator<<(unsigned long long a){putInt(a);return *this;}
OUT& operator<<(unsigned __int128 a){putInt(a);return *this;}
OUT& operator<<(float a){putDouble(a);return *this;}
OUT& operator<<(double a){putDouble(a);return *this;}
OUT& operator<<(long double a){putDouble(a);return *this;}
~OUT(){flush();}
};
}
fastio::IN fin;
fastio::OUT fout;
const int mod=1e9+7;
int fac[200000010],defac[100000010];
template<typename T2,typename T3>
i64 qp(i64 b,T2 po,T3 p){
i64 res=1;
while(po>0){
if(po&1)
res=res*b%p;
b=b*b%p;
po>>=1;
}
return res;
}
void init(int n){
fac[0]=defac[0]=1;
for(int i=1;i<=n;++i){
fac[i]=(i*(i64)fac[i-1])%mod;
}
int lim=n>>1;
defac[lim]=qp(fac[lim],mod-2,mod);
for(int i=lim-1;i>0;--i){
defac[i]=defac[i+1]*(i64)(i+1)%mod;
}
}
long long C(int n,int m){
if(m==0)return 1;
if(m<0||m>n)return 0;
return fac[n]*(i64)defac[m]%mod*(i64)defac[n-m]%mod;
}
// i64 dat[100][100];
i64 T(i64 n,i64 m){
return C(n+m,n)*(n-m+1)%mod*qp(n+1,mod-2,mod)%mod;
}
i64 n=100000000;
i64 a=1,b=3;
i64 res;
i64 f(int num){
return T(n-2,n-num);
}
int main(){
init(200000000);
// fin>>n;
i64 sum=0;
for(int i=1;i<=n;++i){
res+=f(i)*a;
res%=mod;
tie(a,b)=make_tuple(b,(a+b)%mod);
if(i%100000==0){
fout<<i<<" "<<res<<"\n";
fout.flush();
}
}
fout<<res;
// for(int i=0;i<=n;++i){
// for(int j=0;j<=i;++j){
// fout<<T(i,j)<<" ";
// }
// enter;
// }enter;
// for(int _=1;_<=n;++_){
// for(int l=1;l<=n;++l){
// dat[1][l]=0;
// }
// dat[1][_]=1;
// for(int i=2;i<=n;++i){
// for(int j=i;j<=n;++j){
// dat[i][j]=dat[i-1][j]+dat[i][j-1];
// }
// }
// // for(int i=1;i<=n;++i){
// // for(int j=1;j<=n;++j){
// // fout<<dat[i][j]<<" ";
// // }
// // enter;
// // }
// // enter;
// sum+=dat[n][n];
// fout<<"! "<<dat[n][n]<<" "<<T(n-2,n-_)<<"\n";
// }
// fout<<"! "<<sum;
return 0;
}