20443번 - 배드민턴 대회

운동 동아리 회장을 맡고 있는 현아는 동아리 배드민턴 대회를 열려고 한다.

현아는 4의 배수를 좋아하여 참가자의 수가 4로 나누어 떨어지기를 바란다.

따라서, 참가자들의 인원이 4의 배수가 아닌 경우, 4의 배수가 되도록 무작위로 3명 이하의 참가자를 추첨에서 제외하고 상대 추첨을 시작한다.

참가자들은 각자 1번부터 N번까지의 번호가 매겨져 있으며, 상대 추첨은 아래와 같이 진행된다.

1. 추첨에서 제외되지 않은 참가자들의 번호표를 상자에 넣고 섞는다.
2. 각자 상자에서 무작위로 번호표를 하나씩 뽑아 자신의 상대 번호를 확인한다.

이 때, 현아는 무작위로 3명 이하의 참가자를 추첨에서 제외한 후, 참가자들이 모두 본인의 번호가 아닌 번호표를 뽑는 경우의 수가 궁금하다.

참가 인원이 많아 피곤한 현아를 위해 모든 경우의 수를 구하는 프로그램을 만들어주자!

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

첫째 줄에 답을 1,000,000,007으로 나눈 나머지를 출력한다.

참가자는 본인이 뽑은 상대와 한 경기, 본인을 뽑은 상대와 경기를 진행하게 된다.

서로를 뽑았을 경우, 같은 상대와 두 경기를 진행하게 된다.