// tested by Hightail - https://github.com/dj3500/hightail import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.math, std.typecons, std.container, core.bitop; immutable mod = 10^^9 + 7; int n; void main() { scan(n); if (n <= 2) { writeln(1); return; } auto dp = new int[][](n + 1, 3); dp[1][0] = 1; dp[2][1] = 1; dp[3][0] = dp[3][1] = dp[3][2] = 1; foreach (i ; 4 .. n + 1) { foreach (s ; 0 .. 3) { foreach (st ; 0 .. 3) { if (s == st) continue; (dp[i][s] += dp[i - s - 1][st]) %= mod; } } } int ans; foreach (s ; 0 .. 3) { (ans += dp[n][s]) %= mod; } writeln(ans); } void scan(T...)(ref T args) { string[] line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront(); } assert(line.empty); }