#include #include typedef uint64_t bigint; int const M = 2020; #define mod 1000000007 bigint f[2][M][M], g[2][M]; bigint C[M][M]; void initC(){ bigint *p, *q; for(int n = 0; n < M; ++n){ C[n][0] = 1; p = &C[n][0]; q = &C[n - 1][0]; for(int i = 1; i <= n; ++i){ p[i] = q[i] + q[i - 1]; p[i] %= mod; } } } void initFG(){ g[0][1] = 1; g[1][1] = 1; f[0][1][1] = 1; f[1][1][1] = 1; g[0][0] = 1; g[1][0] = 1; bigint *p, *q, *r, *s; for(int n = 2; n <= 2016; ++n){ p = &f[0][n][0]; q = &C[n-1][0]; r = &g[0][0]; s = &g[0][0]; for(int i = 2; i <= n; i += 2){ p[i] = q[i - 1] * r[i - 1]; p[i] %= mod; p[i] *= s[n - i]; p[i] %= mod; } p = &f[1][n][0]; q = &C[n-1][0]; r = &g[1][0]; s = &g[0][0]; for(int i = 1; i <= n; i += 2){ p[i] = q[i - 1] * r[i - 1]; p[i] %= mod; p[i] *= s[n - i]; p[i] %= mod; } p = &g[0][n]; q = &f[0][n][0]; r = &g[1][n]; s = &f[1][n][0]; for(int i = 1; i <= n; ++i){ *p += q[i]; *p %= mod; *r += s[i]; *r %= mod; } } } void first_init(){ bigint *p = &f[0][0][0]; for(int N = 2 * M * M, i = 0; i < N; ++i){ p[i] = 0; } p = &g[0][0]; for(int N = 2 * M, i = 0; i < N; ++i){ p[i] = 0; } p = &C[0][0]; for(int N = M * M, i = 0; i < N; ++i){ p[i] = 0; } initC(); initFG(); } int get(int N){ if(2 >= N || 2016 < N){ return 0; } bigint ret = g[0][N] + g[1][N]; ret %= mod; return int(ret); } int main(int argc, char *argv[]){ int N = 0; first_init(); scanf("%d", &N); printf("%d\n", get(N)); return 0; }