점프 쇼다운

문제의 모티브는 비디오 게임 폴 가이즈(Fall Guys)의 미니게임 점프 쇼다운이지만, 뒤에 나오는 게임 시스템과는 관계가 없으므로 지문을 끝까지 읽어야 합니다.

[그림 1]

점프 쇼다운은 [그림 1]과 같이 가운데가 뚫린 원형 게임장에서 즐기는 게임이다. 1번부터 N번까지 N개의 판이 맞물려 하나의 게임장을 이룬다. 게임이 시작된 직후에는 N개의 판이 모두 존재하지만, 시간이 지남에 따라 판들이 순차적으로 사라진다. 마지막에는 정확히 3개의 판이 남고, 이 셋은 게임이 끝날 때까지 절대 사라지지 않는다.

모든 판은 서로 구분할 수 있다. 즉, 1번 판이 사라진 경우와 2번 판이 사라진 경우는 서로 다른 경우이다. 각 판은 시계 방향과 반시계 방향으로 가장 가까운 두 판과 인접한다. 인접한 판이 사라져도 그 다음으로 가까운 판과 인접하게 되지는 않는다. [그림 1]에서 1번 판과 인접한 판은 2번 판과 8번 판이다.

플레이어는 사라지지 않은 판 위에 가만히 서 있거나, 밟고 있는 판과 인접한 판으로 걸어서 이동할 수 있다. 인접한 판이 사라졌다면 그곳으로는 이동할 수 없다. 사라지는 판 위에 가만히 서 있으면 게임에서 탈락한다.

[그림 2]

[그림 2]와 같은 상황을 예로 들면,

• 1 → 2의 순서로 판이 사라지면 1이나 2에 서 있던 플레이어는 3으로 이동할 수 있다.
• 2 → 1의 순서로 판이 사라지면 1에 가만히 서 있던 플레이어는 반드시 탈락할 수밖에 없다.

불가항력으로 탈락하게 된 플레이어는 화가 나서 게임을 그만둘 수 있다. 게임 제작자는 사람들이 게임을 계속 플레이하기를 바라므로, 이렇게 탈락하는 경우가 생기지 않도록 하려고 한다. 판이 사라지는 $P(N, N-3) = N!\div 3!$가지 경우 중에서, 플레이어가 어떻게 이동하더라도 불가항력으로 탈락하지 않는 경우가 몇 가지인지 알아보자.

게임이 시작된 직후의 판의 개수 N이 주어진다.

문제의 정답을 $10^9 + 7$로 나눈 나머지를 출력한다.

• 4 ≤ N ≤ 300