import java.util.Arrays;

public class Euler707 {
    static final long kMod = 1000000007L;
    static final long kPhi = kMod - 1L;

    static class Mat {
        int w;
        int words;
        long[][] row;

        Mat(int w) {
            this.w = w;
            this.words = (w + 63) / 64;
            this.row = new long[w][this.words];
        }
    }

    static void setBit(long[] r, int c) {
        r[c >> 6] |= (1L << (c & 63));
    }

    static boolean getBit(long[] r, int c) {
        return ((r[c >> 6] >> (c & 63)) & 1L) != 0L;
    }

    static Mat identity(int w) {
        Mat I = new Mat(w);
        for (int i = 0; i < w; ++i) {
            setBit(I.row[i], i);
        }
        return I;
    }

    static Mat buildH(int w) {
        Mat H = new Mat(w);
        for (int i = 0; i < w; ++i) {
            setBit(H.row[i], i);
            if (i > 0)
                setBit(H.row[i], i - 1);
            if (i + 1 < w)
                setBit(H.row[i], i + 1);
        }
        return H;
    }

    static Mat add(Mat A, Mat B) {
        Mat C = new Mat(A.w);
        for (int i = 0; i < A.w; ++i) {
            for (int k = 0; k < A.words; ++k) {
                C.row[i][k] = A.row[i][k] ^ B.row[i][k];
            }
        }
        return C;
    }

    static Mat mul(Mat A, Mat B) {
        Mat C = new Mat(A.w);
        for (int i = 0; i < A.w; ++i) {
            long[] acc = new long[A.words];
            for (int wb = 0; wb < A.words; ++wb) {
                long bits = A.row[i][wb];
                while (bits != 0L) {
                    int b = Long.numberOfTrailingZeros(bits);
                    int col = (wb << 6) + b;
                    if (col < A.w) {
                        long[] brow = B.row[col];
                        for (int k = 0; k < A.words; ++k) {
                            acc[k] ^= brow[k];
                        }
                    }
                    bits &= bits - 1L;
                }
            }
            C.row[i] = acc;
        }
        return C;
    }

    static Mat leftMulH(Mat P) {
        Mat R = new Mat(P.w);
        for (int i = 0; i < P.w; ++i) {
            long[] acc = Arrays.copyOf(P.row[i], P.words);
            if (i > 0) {
                for (int k = 0; k < P.words; ++k)
                    acc[k] ^= P.row[i - 1][k];
            }
            if (i + 1 < P.w) {
                for (int k = 0; k < P.words; ++k)
                    acc[k] ^= P.row[i + 1][k];
            }
            R.row[i] = acc;
        }
        return R;
    }

    static int rankGf2(Mat A_in) {
        Mat A = new Mat(A_in.w);
        for (int i = 0; i < A.w; i++) {
            System.arraycopy(A_in.row[i], 0, A.row[i], 0, A.words);
        }

        int r = 0;
        for (int c = 0; c < A.w && r < A.w; ++c) {
            int piv = -1;
            for (int i = r; i < A.w; ++i) {
                if (getBit(A.row[i], c)) {
                    piv = i;
                    break;
                }
            }
            if (piv == -1)
                continue;

            if (piv != r) {
                long[] temp = A.row[piv];
                A.row[piv] = A.row[r];
                A.row[r] = temp;
            }

            for (int i = r + 1; i < A.w; ++i) {
                if (getBit(A.row[i], c)) {
                    for (int k = 0; k < A.words; ++k) {
                        A.row[i][k] ^= A.row[r][k];
                    }
                }
            }
            ++r;
        }
        return r;
    }

    static long modPow2(long e) {
        long base = 2L;
        long out = 1L;
        while (e > 0L) {
            if ((e & 1L) != 0L)
                out = (out * base) % kMod;
            base = (base * base) % kMod;
            e >>= 1L;
        }
        return out;
    }

    static long termFromB(Mat Bk, long fibK, int w) {
        int rk = rankGf2(Bk);
        int nullity = w - rk;
        long exp = ((w % kPhi) * (fibK % kPhi)) % kPhi;
        exp = (exp + kPhi - (nullity % kPhi)) % kPhi;
        return modPow2(exp);
    }

    static long sValue(int w, int n) {
        Mat A_prev = identity(w);
        Mat B_prev = buildH(w);
        Mat A_cur = identity(w);
        Mat B_cur = buildH(w);

        long fibPrev = 1L;
        long fibCur = 1L;

        long sum = 0L;
        if (n >= 1)
            sum = (sum + termFromB(B_prev, fibPrev, w)) % kMod;
        if (n >= 2)
            sum = (sum + termFromB(B_cur, fibCur, w)) % kMod;

        for (int k = 3; k <= n; ++k) {
            Mat P = mul(A_cur, A_prev);
            Mat Q = mul(A_cur, B_prev);
            Mat R = mul(B_cur, A_prev);
            Mat S = mul(B_cur, B_prev);
            Mat HP = leftMulH(P);

            Mat A_next = add(add(Q, R), HP);
            Mat B_next = add(S, P);

            long fibNext = (fibCur + fibPrev) % kPhi;
            sum = (sum + termFromB(B_next, fibNext, w)) % kMod;

            A_prev = A_cur;
            B_prev = B_cur;
            A_cur = A_next;
            B_cur = B_next;
            fibPrev = fibCur;
            fibCur = fibNext;
        }

        return sum;
    }

    public static String solve() {
        return Long.toString(sValue(199, 199));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}