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

계단의 수가 입력된다. (십의 십팔승보다 작은 수의 계단이며, 0.5계단같은건 없다.)

오르는 방법의 수를 출력한다.

창의적알고리즘