斐波那契的遞歸和非遞歸，21遞歸：斐波那契

【題目】?
**Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。?
當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的余數是多少。?
輸入格式?
輸入包含一個整數n。?
輸出格式?
輸出一行，包含一個整數，表示Fn除以10007的余數。?
說明：在本題中，答案是要求Fn除以10007的余數，因此我們只要能算出這個余數即可，而不需要先計算出Fn的準確值，再將計算的結果除以10007取余數，直接計算余數往往比先算出原數再取余簡單。?
樣例輸入?
10?
樣例輸出?
55?
樣例輸入?
22?
樣例輸出?
7704?
數據規模與約定?
1 <= n <= 1,000,000。

【分析】?
當n==1或者n==2的時候，Fn=1；?
當n>=3的時候，Fn=Fn-1+Fn-2。

import java.math.BigInteger;
import java.util.*;public class Lanq {public static void main(String[] args) {Fibonacci();}public static void Fibonacci() {Scanner sc = new Scanner(System.in);int n=sc.nextInt();int a[]=new int[1000001];a[0]=0;a[1]=1;a[2]=1;for(int i=3;i<=n;i++){a[i]=a[i-1]%10007+a[i-2]%10007;}System.out.println(a[n]);}
}