#include #include using namespace std; const int mod = 1e9+7; int main(void){ int n; long long dp[100000][4]; queue memo[4]; cin >> n; if(n==1){ cout << "1" << endl; return 0; } if(n == 2){ cout << "2" << endl; return 0; } memo[1].push(1); memo[2].push(0); memo[3].push(0); memo[1].push(0); memo[2].push(1); memo[3].push(0); memo[1].push(1); memo[2].push(1); memo[3].push(1); long long m[5][4]; for(int i=4; i<=n; i++){ m[1][1] = memo[1].front(); m[1][2] = memo[2].front(); m[1][3] = memo[3].front(); memo[1].pop(); memo[2].pop(); memo[3].pop(); m[2][1] = memo[1].front(); m[2][2] = memo[2].front(); m[2][3] = memo[3].front(); memo[1].pop(); memo[2].pop(); memo[3].pop(); m[3][1] = memo[1].front(); m[3][2] = memo[2].front(); m[3][3] = memo[3].front(); memo[1].pop(); memo[2].pop(); memo[3].pop(); m[4][3] = (m[1][2] + m[1][1])%mod; m[4][2] = (m[2][1] + m[2][3])%mod; m[4][1] = (m[3][2] + m[3][3])%mod; memo[1].push(m[2][1]); memo[2].push(m[2][2]); memo[3].push(m[2][3]); memo[1].push(m[3][1]); memo[2].push(m[3][2]); memo[3].push(m[3][3]); memo[1].push(m[4][1]); memo[2].push(m[4][2]); memo[3].push(m[4][3]); } memo[1].pop(); memo[2].pop(); memo[3].pop(); memo[1].pop(); memo[2].pop(); memo[3].pop(); cout << (memo[1].front()+memo[2].front()+memo[3].front())%mod << endl; return 0; }