sicily 1001. Fibonacci 2

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1001. Fibonacci 2

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Given an integer n, your goal is to compute the last Fn mod (10^9 + 7).

Input

The input test file will contain a single line containing n (n ≤ 2^31-1).

There are multiple test cases!

Output

For each test case, print the Fn mod (10^9 + 7).

Sample Input

aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQEAYABgAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAARABIDASIAAhEBAxEB/8QAGAABAAMBAAAAAAAAAAAAAAAAAAMFBwT/xAAlEAACAQQCAQMFAAAAAAAAAAABAgMABAURBiESIjFBMjZxdbP/xAAYAQACAwAAAAAAAAAAAAAAAAAAAwEEBf/EABsRAQEAAgMBAAAAAAAAAAAAAAEAAgMEEyFh/9oADAMBAAIRAxEAPwDQeRW+SyVnctBIkiiScOk87qm0ciP0aZWA8dkEDZA2fcGPCWPI+PXkUt3GIcQjkyQxTGdtMrAhUVQO5CraVd/UB1pa7cnHmbaW5hjxEktoZJJGulnjChWYsT4lvLoHvr3B1vommvuQYaSe/jGSxrW9yXEiCWIiTe9eWohvs/LH8n5ocDh9jlnsER+zt+9wDE9G0uKWO4hSaGRJIpFDI6MCrKewQR7ilVfFPs7B/r4P5rStB8ZJW9KUqIlKUoi//9k=" alt="" /> Copy sample input to clipboard 

9

Sample Output

34

用矩阵快速幂的方法，具体可见： http://blog.csdn.net/ACdreamers/article/details/25616461

#include <iostream>

using namespace std;

#define M 1000000007

struct Matrix{
    long long v[][];
};

Matrix matrixMul(Matrix a, Matrix b) {
    Matrix temp;
    for (int i = ; i != ; i++) {
        for (int j = ; j != ; j++) {
            temp.v[i][j] = ;
            for (int k = ; k != ; k++) {
                temp.v[i][j] += a.v[i][k] * b.v[k][j];
                temp.v[i][j] %= M;
            }
        }
    }
    return temp;
}

Matrix power(Matrix a, Matrix b, long long n) {
    while (n) {
        if (n & ) {
            b = matrixMul(b, a);
        }
        n >>= ;
        a = matrixMul(a, a);
    }
    return b;
}

int main(int argc, char* argv[])
{
    Matrix a = {, , , }, b = {, , , };
    long long n;
    while (cin >> n) {
        if (n == )
            cout <<  << endl;
        else {
            Matrix result = power(a, b, n - );
            cout << result.v[][] << endl;
        }
    }

    return ;
}