Badminton Tournament
Time limit1sMemory limit1024 MB
Count the number of ways to remove at most 3 of N participants and then have everyone remaining draw a tag that is not their own.
- Level
Medium5 of 10
- Topics
- Combinatorics, Math, Dynamic programming, Implementation
- Solved
- No attempts yet
Problem
Hyeona, the president of a sports club, is holding a badminton tournament for the club.
Hyeona likes multiples of 4, so she wants the number of participants to be divisible by 4.
Therefore, if the number of participants is not a multiple of 4, she randomly excludes at most 3 participants from the draw so that the number becomes a multiple of 4, and then starts drawing opponents.
The participants are numbered from 1 to N, and the opponent draw proceeds as follows.
- Put the number tags of the participants who were not excluded from the draw into a box and mix them.
- Each participant randomly draws one number tag from the box and checks the number of their opponent.
Hyeona is curious about the number of ways this can happen: after randomly excluding at most 3 participants from the draw, all participants draw a number tag that is not their own number.
Let's write a program that finds the number of all such cases for Hyeona, who is tired because there are many participants!
Input
The first line gives an integer N. (4 ≤ N ≤ 100)
Output
Print the answer modulo 1,000,000,007 on the first line.
Hint
A participant plays one match against the opponent they drew, and one match against the opponent who drew them.
If two participants draw each other, they play two matches against the same opponent.