using System; using System.Linq;//リストの使用 using System.Collections.Generic; using System.Text;//テキストの高速出力に必要 class Program { static void Main() { long n = long.Parse(Console.ReadLine()); long mod = 1000000007; long[,] multipleMatrix = new long[,] { {1,1}, {1,0} }; long[,] firstMatrix = new long[,] { {1}, {1} }; long[,] subMatrix = MatrixProductRepeat(multipleMatrix,n-1,mod); long[,] answerMatrix = MatrixProduct(subMatrix,firstMatrix,mod); Console.WriteLine((answerMatrix[0,0]*answerMatrix[1,0])%mod); } static long[,] MatrixProductRepeat(long[,] originalMatrix, long mul, long p) {//平方行列のmul乗(mod p)を返す //ただし、mod=0でそのまま返す long matrixLength = originalMatrix.GetLength(0); long[,] answerMat = new long[matrixLength,matrixLength];//配列は、=引数とせずnewとしないと引数元も変更される for(int i = 0; i < matrixLength; i++) { for(int j = 0; j < matrixLength; j++) { answerMat[i,j] = originalMatrix[i,j]; } } List multipleList = new List();//0は元の行列、1は積の行列をかける long memo = mul; while(memo > 1) { if(memo % 2 == 1) { multipleList.Add(0); memo--; }else { multipleList.Add(1); memo /= 2; } } for(int i = multipleList.Count()-1; i >= 0; i--) { if(multipleList[i] == 0) answerMat = MatrixProduct(answerMat,originalMatrix,p); else answerMat = MatrixProduct(answerMat,answerMat,p); } if(mul == 0)//0乗では単位行列を返す { for(int i = 0; i < matrixLength; i++) { for(int j = 0; j < matrixLength; j++) { if(i == j) answerMat[i,j] = 1; else answerMat[i,j] = 0; } } } return answerMat; } static long[,] MatrixProduct(long[,] originalMatrixA, long[,] originalMatrixB, long p) //行列の積(mod p)を返す //ただし、p=0でそのまま返す { long matrixLengthH = originalMatrixA.GetLength(0); long matrixLengthW = originalMatrixB.GetLength(1); long matrixLengthSub = originalMatrixA.GetLength(1); if(originalMatrixA.GetLength(1) == originalMatrixB.GetLength(0))//これを満たさないと行列計算は不可能 { matrixLengthSub = originalMatrixA.GetLength(1); } if(p != 0) { for(int i = 0; i < originalMatrixA.GetLength(0); i++) { for(int j = 0; j < originalMatrixA.GetLength(1); j++) { originalMatrixA[i,j] %= p; } } for(int i = 0; i < originalMatrixB.GetLength(0); i++) { for(int j = 0; j < originalMatrixB.GetLength(1); j++) { originalMatrixB[i,j] %= p; } } } long[,] answerM = new long[matrixLengthH, matrixLengthW]; for(long lineM = 0; lineM < matrixLengthH; lineM++) { for(long rowM = 0; rowM < matrixLengthW; rowM++) { long ansMemo = 0; for(long i = 0; i < matrixLengthSub; i++) { ansMemo += originalMatrixA[lineM,i] * originalMatrixB[i,rowM];//成分計算 if(p != 0) ansMemo %= p; } answerM[lineM,rowM] = ansMemo; } } return answerM; } }