Consider a sequence of length (n) with associated value (F_n). This value can be interpreted as a count, particularly in tiling problems where each tile has a distinct color. This interpretation allows transformation into a solvable form.

The generating function for the tiling sequence is given by: [\frac{x}{1-x-x^2}]

The overall generating function becomes: [\frac{1}{1-\frac{x}{1-x-x^2}}]

Simplifying this expression by multiplying numerator and denominator by (1-x-x^2): [\frac{1-x-x^2}{1-2x-x^2}]

This can be rewritten as: [1+\frac{x}{1-2x-x^2}]

Performing partial fraction decomposition: [\frac{A}{x-x_1}+\frac{B}{x-x_2}]

Where: [\begin{cases}x_1=\sqrt{2}-1 \ x_2=-1-\sqrt{2} \ A=\frac{\sqrt{2}-1}{2\sqrt{2}} \ B=\frac{\sqrt{2}+1}{2\sqrt{2}} \end{cases}]

Rewriting in terms of reciporcal forms: [\frac{A/x_1}{x/x_1-1}+\frac{B/x_2}{x/x_2-1}]

Converting to negative forms suitable for series expansion: [\frac{-A/x_1}{1-x/x_1}+\frac{-B/x_2}{1-x/x_2}]

Extracting the coefficient of (x^n): [[x^n]\frac{-A/x_1}{1-x/x_1}+[x^n]\frac{-B/x_2}{1-x/x_2}]

This yields: [-\frac{A}{x_1^{n+1}}-\frac{B}{x_2^{n+1}}]

Substituting known values and factoring: [\frac{1}{2\sqrt{2}}\left((1+\sqrt{2})^n-(1-\sqrt{2})^n\right)]

For modular arithmetic with (P = 10^9 + 7), the square root of 2 modulo (P) is 940286407.

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read_input(T& value) {
    value = 0;
    char ch = getchar();
    int sign = 1;
    while(!('0' <= ch && ch <= '9')) {
        if(ch == '-') sign = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        value = value * 10 + ch - '0';
        ch = getchar();
    }
    value *= sign;
}

template <typename T, typename... Args>
inline void read_input(T& t, Args&... args) {
    read_input(t);
    read_input(args...);
}

const long long MOD = 1000000007;
const long long SQRT_2_MOD = 940286407;

long long modular_power(long long base, long long exp) {
    long long result = 1;
    while(exp > 0) {
        if(exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    long long n = 0;
    char digit;
    while(cin >> digit) {
        n = (n * 10 + digit - '0') % (MOD - 1);
    }
    
    long long term1 = modular_power(1 + SQRT_2_MOD, n);
    long long term2 = modular_power(1 - SQRT_2_MOD + MOD, n);
    long long difference = (term1 - term2 + MOD) % MOD;
    
    long long denominator_inverse = modular_power(2 * SQRT_2_MOD, MOD - 2);
    cout << (difference * denominator_inverse) % MOD << endl;
    
    return 0;
}