Count Collisions of Monkeys on a Polygon
There is a regular convex polygon with n vertices. The vertices are labeled from 0 to n - 1 in a clockwise direction, and each vertex has exactly one monkey.
Simultaneously, each monkey moves to a neighboring vertex. A collision happens if at least two monkeys reside on the same vertex after the movement or intersect on an edge.
Return the number of ways the monkeys can move so that at least one collision happens. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
n = 3Output
6There are 8 total possible movements, and 6 of them cause at least one collision.
Example 2
Input
n = 4Output
14Out of all possible movements for 4 monkeys, 14 cause at least one collision.
Constraints
- 3 <= n <= 10^9