승리 퍼레이드

데스 스타 파괴와 제국과의 승리를 기념해 반란군이 퍼레이드를 열었다. 퍼레이드에는 $n$명이 참가한다. 각 참가자는 일정한 수의 훈장을 받았으며, 어떤 두 사람도 훈장 수가 같지 않다.

참가자들은 한 명씩 광장에 나와 한 줄로 선다. 새로 나온 사람은 이미 서 있는 모든 사람 옆을 지나간다. 자기보다 훈장을 많이 받은 사람 옆을 지날 때마다 멈춰서 경례해야 한다. 경례 한 번에는 규정으로 정한 같은 시간이 든다.

준비 단계에서 광장에 설 순서는 엄격히 정해 두었다. 그러나 퍼레이드 당일 장비가 광장 입구 가운데 하나를 막는다. 왼쪽 입구가 막힐지 오른쪽 입구가 막힐지는 아직 알 수 없다. 퍼레이드 일정은 초 단위로 맞춰져 있으므로, 어느 쪽에서 입장하든 모두가 들어오는 데 걸리는 시간은 같아야 한다. 전체 소요 시간은 경례 횟수에 따라서만 정해진다.

오른쪽 입구가 막힌 경우, 가장 왼쪽에 서야 하는 사람이 먼저 나온다. 다음으로 두 번째에 서야 하는 사람이 이미 서 있는 첫 번째 사람 옆을 지나 나온다. 이런 식으로 이어진다. 왼쪽 입구가 막힌 경우에는 가장 오른쪽에 서야 하는 사람이 먼저 나오고, 오른쪽에서 두 번째에 서야 하는 사람이 이미 서 있는 가장 오른쪽 사람 옆을 지나 나온다. 이런 식으로 이어진다.

양쪽에서 입장할 때 걸리는 시간이 같은 배치만 의미가 있다. 그런 배치의 개수를 구하라.

입력은 한 줄이며, 정수 $n$ ($1 \le n \le 500$)이 주어진다.

경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

훈장 수가 각각 1, 2, 3, 4인 두 번째 예제에서 관심 있는 배치는 다음과 같다.

• $1$, $4$, $3$, $2$
• $2$, $3$, $4$, $1$
• $2$, $4$, $1$, $3$
• $3$, $1$, $4$, $2$
• $3$, $2$, $1$, $4$
• $4$, $1$, $2$, $3$