28243번 - 조별 수업

문제

송도고등학교의 박상진 선생님은 조별 수업에서 버스를 타는 학생은 없고 모두가 협력할 수 있는 획기적인 방법을 고안해내셨다!

박상진 선생님의 획기적인 방법을 사용하지 않은 보통의 조별 수업 상황이다.

그 방법은 바로 조를 특별한 방식으로 짜는 것이다.

1ドル$번부터 $n$번까지의 번호가 배정된 학생들 $n$명이 임의의 순서로 일렬로 서 있을 때, 이를 연속한 구간 여러 개로 나누어 조를 짠다. 이때 모든 구간에 대해 각 구간의 길이가 구간에 속한 학생들의 번호 중 최솟값과 같아야 올바른 조 짜기 방법이 된다.

박상진 선생님은 학생들이 일렬로 서 있을 수 있는 모든 경우에 대한 올바른 조 짜기 방법의 수의 합을 알고 싶다. 선생님을 도와 이를 구하는 프로그램을 작성하여라.

단, 답이 너무 커질 수 있으니 답을 10ドル^9+7$로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 학생 수 $n$이 주어진다.

출력

학생들이 일렬로 서 있을 수 있는 모든 경우에 대한 올바른 조 짜기 방법의 수의 합을 10ドル^9+7$로 나눈 나머지를 출력하여라.

제한

• 1ドル\le n\le 1,000円$.

힌트