1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 100010,mod = 1000000007;
ll f[maxn]={1,2,4,7},g[maxn]={1,3,8,18};
int main(){
    for(int i=3;i<=maxn;i++){
        f[i] = (f[i-1]+f[i-2]+f[i-3]) % mod;
        g[i] = (f[i]+g[i-1]+g[i-2]+g[i-3]) % mod;
    }
    int n;
    cin>>n;
    cout<<g[n]<<endl;
    return 0;
} 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX