비밀 연구소

군사 기지 바스커빌에는 비밀 다층 연구소가 있다. 각 층에는 정확히 $n$개의 번호가 매겨진 방이 있다. 방 $i$와 방 $j$의 쌍마다 방 $i$에서 방 $j$로 이어지는 복도는 많아야 하나이다. 각 복도는 한 방향으로만 지날 수 있다.

어떤 방에서 나온 뒤에 그 방으로 다시 돌아갈 수 없는 층을 안전한 층이라고 한다. 연구소는 안전한 층만으로 이루어져 있으며, 모든 층은 서로 달라야 한다. 두 층이 다르다는 것은 어떤 $i$, $j$가 존재해서 한 층에는 방 $i$에서 방 $j$로 가는 복도가 있고 다른 층에는 그 복도가 없다는 뜻이다.

셜록과 왓슨 박사가 이 연구소에 최대 몇 개의 층을 둘 수 있는지 알아내도록 도와라. 답이 매우 클 수 있으므로, 최대 층 수를 $10^9+7$로 나눈 나머지를 구하라.

입력은 한 줄이며, 층마다 있는 방의 개수 $n$ ($1 \le n \le 6500$)이 주어진다.

가능한 최대 층 수를 $10^9+7$로 나눈 나머지를 출력하라.

아래 그림은 예제에 나온 가능한 층을 모두 보여 준다.