의도된 시간복잡도
🔒시간 제한
1.000 S메모리 제한
512 MB제출 수
2정답 수
2정답률
100.000%
문제 설명
피보나치 수 $F_n$은 다음으로 정의되는 수열이다.
$0$번째 항 $F_0 = 0$을 시작으로 초항을 나열해보면 다음과 같을 것이다.
- $0, 1, 1, 2, 3, 5, 8, 13, ...$
$n$이 주어질 때, $n$번째 피보나치 수 $F_n$을 구해보자.
입력 설명
첫째 줄에 음이 아닌 정수 $n$이 주어진다. $(0 ≤ n ≤ 10^{18})$
출력 설명
첫째 줄에 $F_n$을 출력한다.
단, 수가 너무 커질 수 있으니 $10^9 + 7$로 나눈 나머지를 출력한다.
예시 1
입력
100
출력
687995182
기여
만든 사람 : pill27211