자연수 N을 입력받아서 N이하의 자연수 합으로 분할할 수 있는 서로 다른 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어 N = 5인 경우의 서로 다른 분할 방법은 다음과 같이 총 7가지가 존재합니다.

• 5

• 4 + 1

• 3 + 2

• 3 + 1 + 1

• 2 + 2 + 1

• 2 + 1 + 1 + 1

• 1 + 1 + 1 + 1 + 1

입력

첫 번째 줄에 자연수 N이 주어진다.

출력

N의 자연수 분할 방법의 개수를 1,000,000,007로 나눈 나머지를 첫째 줄에 출력한다.

제한 사항

• 1 ≤ N ≤ 1,000

One integer \(N\) (\(1 \le N \le 1000\)).

Print the number of partitions of \(N\) modulo \(1{,}000{,}000{,}007\).

riseoj 작성

출처 Online Judge > GoldOJ