import java.util.*; public class Main { private static final int MOD = 1000000007; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { long n = scanner.nextLong(); long[][] ret = matrixN(new long[][]{{1,1},{1,0}}, n - 2); long printRes = (ret[0][0] % MOD + ret[0][1] %MOD) %MOD; System.out.println(printRes); } } public static long[][] matrixN(long[][]a, long n) { long[][] ret = new long[a.length][a[0].length]; for(int i = 0;i < ret.length;i++) { ret[i][i] = 1; } long[][]tmp = a; for(;n > 0; n >>= 1) { if ((n & 1) != 0) { ret = matrixMulti(ret, tmp); } tmp = matrixMulti(tmp, tmp); } return ret; } public static long[][] matrixMulti(long[][]a, long[][]b) { long[][] ret = new long[a.length][b[0].length]; for(int i = 0;i < a.length;i++) { for(int j = 0;j < b[0].length;j++) { for(int k = 0; k < b.length;k++) { ret[i][j] = (ret[i][j] % MOD + a[i][k] % MOD * b[k][j] ) % MOD; } } } return ret; } }
测试数据会超过int型,所以记得全部切换成long型即可,另外为防止long型溢出,需要按照(a+b)%c=(a%c+b%c)%c控制结果范围。