문제
최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 생각해 보자.
아래 그림은 n 이 4 인 경우의 예 이다.
총 5가지 경우가 존재한다.
그렇다면 계단의 수가 n개일 때는 경우의 수가 몇가지 존재할까? 답이 커질 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.
입력
입력의 첫 줄은 계단의 갯수 (1 <= N <= 1,000,000,000)이 주어진다.
출력
계단 N개를 오를 수 있는 경우의 수를 10억 7로 나눈 나머지를 출력한다.
힌트
예제 입력
4
예제 출력
5