斐波那契数列 (FibonacciSequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契 (LeonardoFibonacci) 以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1,1,2,3,5,8,13,21,⋯

在数学上，斐波那契数列被以如下的递推方法定义：

fib(1)=1;

fib(2)=1;

fib(n)=fib(n−1)+fib(n−2),n>2.

我们想要知道斐波那契数列的某一项，请你编程解决这个问题。

考虑到结果可能会很大，我们要求你将结果对 109+7 取模后再输出。

a 对 b 取模的含义是 a 除以 b 的余数。

输入格式:

一行，一个正整数 n(1≤n≤106)

输出格式:

一行，一个整数 fib(n)mod(109+7)，代表斐波那契数列的第 n 项对 109+7 取模后的结果

输入样例1:

1

输出样例1:

1

输入样例2:

100

输出样例2:

687995182

import java.util.Scanner;

public class Main {
    public static int  fibonacci(int n) {

        int f=1,f1=1,f2=1;
        for (int i = 3; i <= n; i++) {
            f=(f1+f2)%1000000007;   //让斐波那契数列的每一项的余数进行斐波那契数列规则相加
            f2=f1;                  // 这样就可以避免数据太大表示不了 减少运行时间
            f1=f;
        }
       return f;
    }

    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
        System.out.println(fibonacci(in.nextInt()));

    }
}