f[i][j]表示填满前i列且第i + 1列填了j个
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10, mod = 1000000007;
LL f[N][3];
int n;
int main()
{
cin >> n;
f[1][0] = 1;
f[1][1] = 2;
f[1][2] = 1;
for (int i = 2; i <= n; i++){
//第i + 1列一个没填 = 一个竖着的长条(因为之前第i - 1列填满但是第i列一个没填) + 在填第i - 1列的时候第i列已经被填满了
f[i][0] = (f[i - 1][0] + f[i - 1][2]) % mod;
//第i + 1列填了一个 = 一个直角图形(因为之前第i - 1列填满但是第i列一个没填) + 一个横着的长条(在填第i - 1列的时候第i列已经填了一个,所以在直角图形空的那个地方补一个横着的长条,上下两种情况)
f[i][1] = (f[i - 1][0] * 2 + f[i - 1][1]) % mod;
//第i + 1列一个填完了 = 两个个竖(横也行)着的长条(因为之前第i - 1列填满但是第i列一个没填) + 一个直角图形(在填第i - 1列的时候第i列已经填了一个,再补一个刚好能合一起的直角就行)
f[i][2] = (f[i - 1][0] + f[i - 1][1]) % mod;
}
cout << f[n][0] << endl;
return 0;
}