How to seat?#5980
An organization is hosting an event for pairs of twins, each pair consisting of a brother and a sister. During the banquet, they plan to seat everyone around a circular table. The seating must alternate between boys and girls, and no twin pair should sit next to each other.
How many distinct seating arrangements are possible under these conditions? Two arrangements are considered different if you cannot rotate one arrangement to exactly match the other.
The input consists of a single line containing an integer (0 \leq N \leq 500).
Output a single line with the number of valid seating arrangements, given modulo (10^9+9).
Example 1