### Problem Statement

You are trying to predict the outcome of a race between n runners, numbered from 0 to n - 1.You are given two int[]s, first and second. It is guaranteed that for all i, the runner numbered first[i] will always beat the runner numbered second[i]. Determine how many final orderings are possible, modulo 1,000,003. If the information is contradictionary, return 0. Runners are never tied.

### Definition

 Class: RaceOrdering Method: countOrders Parameters: int, int[], int[] Returns: int Method signature: int countOrders(int n, int[] first, int[] second) (be sure your method is public)

### Constraints

-n will be between 1 and 30, inclusive.
-first and second will each contain between 0 and 15 elements, inclusive.
-first and second will contain the same number of elements.
-Each element of first and second will be between 0 and n - 1, inclusive.
-first[i] does not equal second[i] for all i between 0 and m - 1, inclusive, where m is the number of elements in first and second.

### Examples

0)

 `3` `{1}` `{2}`
`Returns: 3`
 Contestant 1 beat contestant 2, so the valid orders are 012, 102 and 120.
1)

 `4` `{0, 0}` `{1, 2}`
`Returns: 8`
 Contestant 0 beat contestants 1 and 2, but there is no information on contestant 3. The valid orderings are 3012, 3021, 0312, 0321, 0132, 0231, 0123 and 0213.
2)

 `10` `{1, 2, 3}` `{2, 3, 1}`
`Returns: 0`
 There is no way to satisfy this cycle.
3)

 `30` `{}` `{}`
`Returns: 90317`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7703

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10787&pm=7703

bmerry

#### Testers:

PabloGilberto , Yarin , ivan_metelsky

#### Problem categories:

Dynamic Programming, Graph Theory, Simple Math