// URL: https://yukicoder.me/problems/no/314 import std.algorithm, std.array, std.bitmanip, std.container, std.conv, std.format, std.functional, std.math, std.range, std.traits, std.typecons, std.stdio, std.string; version(unittest) {} else void main() { int N; io.getV(N); auto dp = new mint[][](N+1, 3); dp[1][1] = 1; foreach (i; 2..N+1) { dp[i][0] = dp[i-1][1]+dp[i-1][2]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][1]; } io.put(dp[N].sum); } const mod = 10^^9+7; alias mint = ModInt!mod; pure nothrow @safe { T powr(alias pred = "a*b", T, U)(const T a, U n, T one) if (isIntegral!U) { auto b = T(a); alias predFun = binaryFun!pred; if (n == 0) return one; auto r = one; for (; n > 0; n >>= 1) { if (n&1) r = predFun(r, b); b = predFun(b, b); } return r; } T powr(alias pred = "a*b", T, U)(const T a, U n) if (isIntegral!U) { return powr!(pred, T, U)(a, n, T(1)); } } pure nothrow @nogc @safe { auto lowerBoundBy(alias conv = "a", alias comp = "a tuple(e, convFun(e))).assumeSorted!((a, b) => compFun(a[1], b[1])); } } pure nothrow @nogc @safe { pragma(inline) { T cdiv(T)(const T a, const T b) { return (a+b-1)/b; } T pmod(T)(const T a, const T b) { return a >= 0 ? a%b : a%b+b; } } ExtGcdResult!T extGcd(T)(const T a, const T b) { if (a == 0) { return ExtGcdResult!T(T(b), T(0), T(1)); } else { auto r = extGcd(b%a, a); return ExtGcdResult!T(r.gcd, r.y-(b/a)*r.x, r.x); } } private struct ExtGcdResult(T) { T gcd, x, y; } } struct ModInt(int m) { pure nothrow @nogc @safe { this(T)(T v) if (isIntegral!T) { i = nm(v); } this(ref return scope const Mint v) { i = v.i; } bool opEquals(T)(T v) const if (isIntegral!T) { return i == v; } bool opEquals(const Mint v) const { return i == v.i; } ref Mint opAssign(T)(T v) if (isIntegral!T) { i = nm(v); return this; } ref Mint opAssign(const Mint v) { i = v.i; return this; } Mint opUnary(string op: "-")() const { return Mint(-i); } static if (m < int.max/2) { Mint opBinary(string op: "+")(int r) const { auto m = Mint.init; m.i = nm(i+r); return m; } Mint opBinary(string op: "+")(const Mint r) const { auto m = Mint.init; m.i = nmp(i+r.i); return m; } ref Mint opOpAssign(string op: "+")(int r) { i = nm(i+r); return this; } ref Mint opOpAssign(string op: "+")(const Mint r) { i = nmp(i+r.i); return this; } } else { Mint opBinary(string op: "+")(int r) const { auto m = Mint.init; m.i = nm(l+r); return m; } Mint opBinary(string op: "+")(const Mint r) const { auto m = Mint.init; m.i = nmp(l+r.i); return m; } ref Mint opOpAssign(string op: "+")(int r) { i = nm(l+r); return this; } ref Mint opOpAssign(string op: "+")(const Mint r) { i = nmp(l+r.i); return this; } } Mint opBinary(string op: "-")(int r) const { return Mint(i-r); } Mint opBinary(string op: "-")(const Mint r) const { return Mint(i-r.i); } ref Mint opOpAssign(string op: "-")(int r) { i = nm(i-r); return this; } ref Mint opOpAssign(string op: "-")(const Mint r) { i = nm(i-r.i); return this; } Mint opBinary(string op, T)(T r) const if ((op == "+" || op == "-") && isIntegral!T && !is(T == int)) { return Mint(mixin("l"~op~"r")); } ref Mint opOpAssign(string op, T)(T r) if ((op == "+" || op == "-") && isIntegral!T && !is(T == int)) { i = nm(mixin("l"~op~"r")); return this; } Mint opBinary(string op: "*", T)(T r) const if (isIntegral!T) { auto m = Mint.init; m.i = nm(l*r); return m; } Mint opBinary(string op: "*")(const Mint r) const { auto m = Mint.init; m.i = nmp(l*r.i); return m; } ref Mint opOpAssign(string op: "*", T)(T r) if (isIntegral!T) { i = nm(l*r); return this; } ref Mint opOpAssign(string op: "*")(const Mint r) { i = nmp(l*r.i); return this; } ref Mint opUnary(string op: "++")() { i = nmp(i+1); return this; } ref Mint opUnary(string op: "--")() { i = nm(i-1); return this; } Mint opBinary(string op: "^^", T)(T n) if (isIntegral!T) { return powr(this, n, Mint(1)); } Mint opBinary(string op: "/")(const Mint r) const { return Mint(l*r.inv.i); } ref Mint opOpAssign(string op: "/")(const Mint r) { i = nm(l*r.inv.i); return this; } Mint opBinary(string op: "/", T)(T r) const if (isIntegral!T) { return opBinary!op(Mint(r)); } ref Mint opOpAssign(string op: "/", T)(T r) if (isIntegral!T) { return opOpAssign!op(Mint(r)); } Mint inv() const { return Mint(extGcd(i, m).x); } } pure nothrow @safe { string toString() const { return i.to!string; } } private { alias Mint = ModInt!m; version(BigEndian) union { long l; struct { int i2; int i; } } else union { long l; int i; } pragma(inline) pure nothrow @nogc @safe { int nm(T)(T v) const if (isIntegral!T) { return cast(int)pmod(v, m); } int nmp(T)(T v) const if (isIntegral!T) { return cast(int)(v%m); } } } } auto io = IO!()(); import std.stdio; struct IO(alias IN = stdin, alias OUT = stdout) { import std.meta : allSatisfy; import core.stdc.stdlib : exit; void getV(T...)(ref T v) { foreach (ref w; v) get(w); } void getA(T)(size_t n, ref T v) if (hasAssignableElements!T) { v = new T(n); foreach (ref w; v) get(w); } void getC(T...)(size_t n, ref T v) if (allSatisfy!(hasAssignableElements, T)) { foreach (ref w; v) w = new typeof(w)(n); foreach (i; 0..n) foreach (ref w; v) get(w[i]); } void getM(T)(size_t r, size_t c, ref T v) if (hasAssignableElements!T && hasAssignableElements!(ElementType!T)) { v = new T(r); foreach (ref w; v) getA(c, w); } template getS(E...) { void getS(T)(size_t n, ref T v) { v = new T(n); foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");"); } } const struct PutConf { bool newline = true, flush, exit; string floatFormat = "%.10f", delimiter = " "; } void put(alias conf = "{}", T...)(T v) { mixin("const PutConf c = "~conf~"; putMain!c(v);"); } void putB(alias conf = "{}", S, T)(bool c, S t, T f) { if (c) put!conf(t); else put!conf(f); } void putRaw(T...)(T v) { OUT.write(v); OUT.writeln; } private { dchar[] buf; auto sp = (new dchar[](0)).splitter; void nextLine() { IN.readln(buf); sp = buf.splitter; } void get(T)(ref T v) { if (sp.empty) nextLine(); v = sp.front.to!T; sp.popFront(); } void putMain(PutConf c, T...)(T v) { foreach (i, w; v) { putOne!c(w); if (i+1 < v.length) OUT.write(c.delimiter); } static if (c.newline) OUT.writeln; static if (c.flush) OUT.flush(); static if (c.exit) exit(0); } void putOne(PutConf c, T)(T v) { static if (isInputRange!T && !isSomeString!T) putRange!c(v); else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v)); else static if (hasMember!(T, "fprint")) v.fprint(OUT); else OUT.write(v); } void putRange(PutConf c, T)(T v) { auto w = v; while (!w.empty) { putOne!c(w.front); w.popFront(); if (!w.empty) OUT.write(c.delimiter); } } } }