조별 수업

시간 제한1초메모리 제한1024 MB

요약

1부터 n까지 수를 늘어놓은 모든 순열에 대해, 각 구간의 길이가 구간 안 최솟값과 같아지도록 나누는 방법의 수를 모두 더한 값을 10^9+7로 나눈 나머지로 구합니다.

문제

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

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

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

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

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

단, 답이 매우 커질 수 있으므로 답을 $10^9+7$ 로 나눈 나머지를 출력한다.

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

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