Problem Statement  
Cat Taro has a board with N rows and M columns divided into unit cells.
He wants to place some checkers on the board.
Each cell can contain at most one checker.
The following conditions must be fulfilled:

For each row i, there is exactly one cell with a checker among the first left[i] cells of the ith row.

For each row i, there is exactly one cell with a checker among the last right[i] cells of the ith row.

For each column, there is at most one cell with a checker in that column.
You are given the int M and the two int[]s left and right (each with N elements).
Let X be the total number of valid ways to place checkers.
Return the value (X modulo 1,000,000,007).
  Definition   Class:  TaroCheckers  Method:  getNumber  Parameters:  int[], int[], int  Returns:  int  Method signature:  int getNumber(int[] left, int[] right, int M)  (be sure your method is public) 
    Constraints    left will contain between 1 and 50 elements, inclusive.    right and left will contain the same number of elements.    M will be between 2 and 200, inclusive.    Each element of left and right will be between 1 and M, inclusive.    For each valid i, the value left[i]+right[i] will be less than or equal to M.   Examples  0)     Returns: 1  Only one way to place checkers is possible in this case:
(In each row, the first left[i] and the last right[i] cells have a darker background.) 

 1)     2)     3)    {10, 25, 100, 74}  {100, 47, 27, 100}  200 
 Returns: 796178974  
 4)    {21, 99, 87, 12, 138, 16, 78, 36, 98, 40, 57, 10, 61, 100, 8, 110, 96, 9, 69, 110, 14, 71}  {83, 8, 25, 169, 1, 89, 109, 89, 19, 112, 39, 112, 87, 66, 116, 16, 41, 97, 52, 70, 111, 23}  190 
 Returns: 235017573  
 5)    {3, 37, 26, 50, 8, 3, 38, 15, 58, 47, 35, 8, 27, 22, 5}  {19, 26, 62, 15, 84, 13, 6, 46, 22, 53, 23, 8, 29, 55, 6}  102 
 Returns: 528024858  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
