#include #include #include int ptns = 0; int n; /// /// 入力された数字を返す /// /// int ReadNum() { int negate = 0; char c = getchar(); int num = 0; int numCnt = 0; while (c != '\n') { if (c == '-') { negate = 1; } else { num = num * 10 + c - '0'; } c = getchar(); } if (negate == 1) { num *= -1; } return num; } int main() { n = ReadNum(); uint64_t* nums; nums = (uint64_t*)malloc(sizeof(uint64_t) * n); nums[0] = 1; nums[1] = 2; nums[2] = 2; for (int i = 3;i < n;i++) { nums[i] = (nums[i - 3] + nums[i - 2])% 1000000007; } printf("%llu\n",nums[n-1]); }