// yukicoder My Practice // author: Leonardone @ NEETSDKASU #include typedef unsigned long ul; const ul MD = 1000000007UL; // 解説読後 // http://yukicoder.me/problems/882/editorial ul a[1000006]; ul *an = a + 3, *an2 = a + 1, *end = a + 1000005; int main(void) { *an2 = 1UL; while (an != end) { *(an++) = ((*(an - 3)) + (*(an - 4))) % MD; } int n; scanf("%d", &n); printf("%lu\n", a[n + 4]); return 0; }