Problem Statement
There are N football teams in the region. The number N is even. Each team has it own home stadium.
The league committee has decided to organize a short summer league for all N teams. The league should have the following properties:
- The league will consist of exactly two rounds of football matches.
- Each team will play one match in each round.
- Each pair of teams will play each other at most once.
- It is well known that playing at its home stadium gives the team a slight advantage. To keep the league fair, each team must play exactly one home game and one away game.
Count all valid league schedules and return that count modulo 10^9 + 7.
Formally: A match is an ordered pair (home team, away team). A round schedule is an unordered set of matches such that each team appears in exactly one match. A league schedule is an ordered pair of round schedules.
Definition
- Class:
- HomeAwayLeague
- Method:
- matches
- Parameters:
- int
- Returns:
- int
- Method signature:
- int matches(int x)
- (be sure your method is public)
Constraints
- N will be between 4 and 500,000, inclusive.
- N will be even.
Examples
4
Returns: 12
Let's use (X,Y) to denote a match where X is the home team and Y is the away team, i.e., a match played at X's home stadium. Here are three of the twelve distinct valid league schedules: First round: (A,B), (C,D). Second round: (B,C), (D,A). First round: (A,B), (D,C). Second round: (B,D), (C,A). First round: (C,A), (B,D). Second round: (A,B), (D,C). Note that the third schedule can be obtained from the second one by swapping the order of the rounds. These two schedules are considered distinct.
6
Returns: 240
8
Returns: 15120
10
Returns: 1330560
12
Returns: 176299200
14
Returns: 69156896
16
Returns: 116573321
18
Returns: 28210500
20
Returns: 162558033
22
Returns: 513950234
24
Returns: 742109722
26
Returns: 292189190
500000
Returns: 623944634
1750
Returns: 692254544
1044
Returns: 685546564
1540
Returns: 405552029
386
Returns: 769284936
286
Returns: 863638954
218560
Returns: 244378502
278886
Returns: 707028450
393300
Returns: 25770988
246512
Returns: 59741836
279900
Returns: 25393081
442576
Returns: 110915818
413732
Returns: 947210709
441540
Returns: 852768510
491658
Returns: 661561938
414322
Returns: 443057932
471748
Returns: 829114589
449028
Returns: 159750116
406112
Returns: 358542402
402700
Returns: 40765893
489594
Returns: 79550224
469260
Returns: 552298495
419108
Returns: 84098132
418928
Returns: 289154756
423892
Returns: 489589847
485600
Returns: 625422281
410048
Returns: 445472463
429568
Returns: 498078487
420326
Returns: 336312449
454322
Returns: 813967975
433664
Returns: 773966314
428028
Returns: 17595816
430844
Returns: 6657054
478486
Returns: 56532561
493662
Returns: 626335551
441404
Returns: 668742480
487874
Returns: 798619102
499998
Returns: 788359703
359210
Returns: 984387624
1000
Returns: 975860204
220464
Returns: 884801879
5000
Returns: 822163173
42
Returns: 729578447
50000
Returns: 676502078