import std.stdio, std.algorithm, std.array, std.conv, std.typecons; immutable p = 1000000007; void main() { auto N = readln[0 .. $-1].to!ulong; auto M = Matrix(1, 0, 0, 1); auto A = Matrix(1, 1, 1, 0); auto power = 1UL; while (power <= N) { if ((N & power) != 0) M = multiply(A, M); A = multiply(A, A); power *= 2; } writeln((M[2] + M[3]) % p); } // 0 1 // 2 3 alias Matrix = Tuple!(ulong, ulong, ulong, ulong); Matrix multiply(Matrix a, Matrix b) { return Matrix( (a[0]*b[0] + a[1]*b[2]) % p, (a[0]*b[1] + a[1]*b[3]) % p, (a[2]*b[0] + a[3]*b[2]) % p, (a[2]*b[1] + a[3]*b[3]) % p); }