#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 #define INF 987654321 typedef long long lld; // (연속된 짝수개의 0)%2 == (연속된 홀수개의 0)%2 char trace[10]; bool isCorrect(char *s, const int& L){ int i, odd=0, even=0, cnt=0; int oneCount=0; for(i=0; i<L; ++i){ if(s[i] == '0'){ cnt = 0; while(s[i+cnt]=='0') cnt++; if(cnt&1) odd += 1; else even += 1; i += cnt-1; oneCount += cnt==1; } } if(odd == 1 || even == 1) return false; if(oneCount&1) return false; return odd%2 == even%2; } lld f(int pos, const int& L){ if(pos == L){ return isCorrect(trace, L); } int r = 0; trace[pos]='0'; r = (r + f(pos+1, L))%MOD; trace[pos]='1'; r = (r + f(pos+1, L))%MOD; return r; } int main(){ int n; while(~scanf("%d", &n)) printf("%lld\n", f(0, n)); return 0; }