2016 AIME II Problem 13

Beatrix is going to place six rooks on a 6 \times 6 chessboard where both the rows and columns are labeled 1 to 6; the rooks are placed so that no two rooks are in the same row or the same column. The *value* of a square is the sum of its row number and column number. The *score* of an arrangement of rooks is the least value of any occupied square. The average score over all valid configurations is \frac{p}{q}, where p and q are relatively prime positive integers. Find p+q.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.