토끼 수열(1, 1, 2, 3, 5, ...)의 N번째 수를 1,000,000,007로 나눈 나머지로 구하세요. N이 어마어마하게 커요!
힌트: 앞에서부터 차례로 계산하면 시간이 부족해요. 행렬 거듭제곱이나 빠른 두 배 공식(fast doubling)을 찾아보세요.
입력
첫째 줄에 자연수 N이 주어져요. (1 ≤ N ≤ 1,000,000,000,000,000,000)
출력
N번째 수를 1,000,000,007로 나눈 나머지로 출력해요.
토끼 수열(1, 1, 2, 3, 5, ...)의 N번째 수를 1,000,000,007로 나눈 나머지로 구하세요. N이 어마어마하게 커요!
힌트: 앞에서부터 차례로 계산하면 시간이 부족해요. 행렬 거듭제곱이나 빠른 두 배 공식(fast doubling)을 찾아보세요.
첫째 줄에 자연수 N이 주어져요. (1 ≤ N ≤ 1,000,000,000,000,000,000)
N번째 수를 1,000,000,007로 나눈 나머지로 출력해요.
6
8
로그인하면 제출할 수 있어요.