The black and white chess rooks were bored, so they decided to invite their colorful friends to a party.
However, as the evening progressed, many pairs of rooks of different colors started arguing and threatening
To prevent a massacre, you now need to place all the rooks in such a way that no two rooks of different colors attack each other.
You are given the dimensions of the chessboard: ints rows and columns. You are also given a int counts, where counts[i] is the number of rooks of the i-th color you have.
Compute and return the value (X mod 1,000,000,009), where X is the number of valid arrangements of all the given rooks on the given chessboard.
No square of the chessboard may contain more than one rook. Rooks of the same color are undistinguishable.