public class Fib {
    static int MOD = 1000000007;
    static int K = 2;

    static void mul(long A[][], long B[][], long C[][])
    {
        C[0][0] = (A[0][0] * B[0][0]) % MOD;
        C[0][0] = (C[0][0] + A[0][1] * B[1][0]) % MOD;

        C[0][1] = (A[0][0] * B[0][1]) % MOD;
        C[0][1] = (C[0][1] + A[0][1] * B[1][1]) % MOD;

        C[1][0] = (A[1][0] * B[0][0]) % MOD;
        C[1][0] = (C[1][0] + A[1][1] * B[1][0]) % MOD;

        C[1][1] = (A[1][0] * B[0][1]) % MOD;
        C[1][1] = (C[1][1] + A[1][1] * B[1][1]) % MOD;
    }

    static void pow(long A[][], long p, long out[][])
    {
        if (p == 1)
        {
            out[0][0] = A[0][0];
            out[0][1] = A[0][1];
            out[1][0] = A[1][0];
            out[1][1] = A[1][1];
            return;
        }
        if(p%2 != 0)
        {
            long B[][] =
                    {
                            {0, 0},
                            {0, 0}
                    };
            pow(A, p - 1, B);
            mul(A, B, out);
        }
        else
        {
            long X[][] =
                    {
                            {0, 0},
                            {0, 0}
                    };
            pow(A, p >> 1, X);
            mul(X, X, out);
        }
    }

    static long fib(long N)
    {
        if(N==-1)
            return 0;
        if(N==0)
            return 1;
        if(N==1)
            return 1;
        long T[][] =
                {
                        {1, 1},
                        {1, 0}
                };

        if (N == 1)
            return 1;
        long[] F1 = new long[K+1];
        F1[1] = 1;
        F1[2] = 1;

        long RM[][] =
                {
                        {0, 0},
                        {0, 0}
                };
        pow(T, N-1, RM);

        long res = RM[0][1] % MOD;
        res = (res + RM[0][0] ) % MOD;
        return res;
    }
}