계단 오르기(M) - 문제

길동이는 n개의 단으로 구성된 계단을 오르려고 한다. 길동이는 계단을 오를 때 기분에 따라서 한 번에 1단 또는 2단을 올라갈 수 있다. 계단의 크기 n이 주어질 때, 길동이가 이 계단을 올라갈 수 있는 모든 경우의 수 를 구하는 프로그램을 작성하시오. 만약 계단이 3개라면 길동이는 1, 1, 1로 올라가는 법과 1, 2로 올라가는 법, 2, 1 로 올라가는 법의 3가지 서로 다른 방법이 있다. 입력 계단의 수 n이 입력된다(단 n은 100000보다 작은 자연수). 출력 길동이가 계단을 오르는 모든 방법의 수를 출력한다. (좀 크다 싶으면 1e9 + 7 로 나눈 나머지를 출력해, pow 금지)