Zapina

자그레브 근교 크라피나에서 열린 겨울 캠프에서 N명의 젊은 프로그래머가 시즌 후반기를 준비하고 있다. 질서와 규율, 근면을 강조하는 말나르 선생은 프로그래머들에게 한 줄로 서게 하고 각자에게 몇 개의 과제(0개일 수도 있다)를 주었다. 서로 다른 N개의 과제를 모두 나눠 주었으며, 줄에서 i번째 프로그래머는 정확히 i개의 과제를 받으면 행복해한다.

말나르 선생이 과제를 나눠 주는 방식 중에서, 적어도 한 명의 프로그래머가 행복해지는 경우의 수를 구하시오. 두 방식은, 어떤 프로그래머와 과제에 대해 한 방식에서는 그 프로그래머가 그 과제를 받았고 다른 방식에서는 받지 않은 경우가 존재하면 서로 다른 것으로 본다.

첫째 줄에 정수 N (1 ≤ N ≤ 350)이 주어진다.

찾는 경우의 수를 109 + 7로 나눈 나머지를 출력한다.