//斐波那契数列取模1000000007输出
//思想：动态规划（滚动数组）
class Solution {
    public int fib(int n) {
        //滚动数组思想
        final int MOD = 1000000007;
        if(n<2){
            return n;
        }
        int p = 0,q = 0,r = 1;
        for(int i = 2; i<=n; i++){
            p = q;
            q = r;
            r = (p+q)% MOD;
        }
        return r;
        
    }
}