피보나치 수 (행렬 거듭제곱)

N번째 피보나치 수를 10^9+7로 나눈 나머지를 구하라. F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2). N이 최대 10^18이므로 행렬 거듭제곱으로 O(log N)에 구현하라.

[[1,1],[1,0]]^(n-1)의 (0,0) 원소가 F(n)임을 이용한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 10^18)

출력

N번째 피보나치 수를 10^9+7로 나눈 나머지를 출력하라.

예제 입력 1

10

예제 출력 1

55