JOIN

 Problem Statement

Problem Statement for TaroCheckers

### 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 i-th row.
• For each row i, there is exactly one cell with a checker among the last right[i] cells of the i-th 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)

 `{1, 2}` `{2, 1}` `4`
`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)

 `{1, 4, 2}` `{2, 3, 1}` `7`
`Returns: 6`
2)

 `{4, 7, 4}` `{7, 4, 7}` `11`
`Returns: 5760`
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.

This problem was used for:
Single Round Match 613 Round 1 - Division I, Level Three