조별 수업 | cho.sh

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

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

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

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

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

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

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

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