25714번 - 점프 쇼다운

문제의 모티브는 비디오 게임 폴 가이즈(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⁹ + 7로 나눈 나머지를 출력한다.

• 4 ≤ N ≤ 300