### Problem Statement

Suppose you have num different objects and have been given some information about their ordering. The information will be given as a String[] facts whose elements will be of the form "A=B" where A and B are integers between 0 and num-1 inclusive. "0=8" means the 0th object is equal to the 8th object. Given these facts you will return the total possible number of distinct ways the objects could be ordered. For example:

num = 4

facts = {"0=2","1=3"}

Possible orderings: 0=2<1=3, 1=3<0=2, 0=1=2=3

In this case there are 3 possible orderings, so you would return 3. If no facts were given, there would be 75 possible orderings. As seen above, the orderings described here are total orderings. This means, for all pairs of objects, the ordering is specified (one is less than the other, or they are equal). Two orderings are the same if all pairs of objects in each ordering have exactly the same relationship.

### Definition

 Class: PossibleOrders Method: howMany Parameters: int, String[] Returns: long Method signature: long howMany(int num, String[] facts) (be sure your method is public)

### Constraints

-facts will contain between 0 and 50 elements inclusive
-num will be between 2 and 17 inclusive
-Each element of facts will be formatted as (quotes for clarity) "A=B" where

A and B are integers between 0 and num-1 inclusive

A and B will have no extra leading zeros

### Examples

0)

 `4` `{"0=2","1=3"}`
`Returns: 3`
 From above.
1)

 `4` `{}`
`Returns: 75`
 No facts.
2)

 `3` `{"1=1"}`
`Returns: 13`
 Useless fact.
3)

 `3` `{"1=2","2=1"}`
`Returns: 3`
 Redundant facts.
4)

 `17` `{}`
`Returns: 130370767029135901`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4575&pm=1643

brett1479

#### Problem categories:

Dynamic Programming