### Problem Statement

You are given a int[] S containing a set of distinct integers. A sequence is called a p-sequence of S if it satisfies both of the following conditions:

1. It contains each element of S exactly once.

2. For each pair of consecutive sequence elements s1 and s2, (s1 - s2) is not divisible by p.

Return the number of p-sequences of S, modulo 1234567891.

### Definition

 Class: PSequence Method: count Parameters: int[], int Returns: int Method signature: int count(int[] S, int p) (be sure your method is public)

### Constraints

-S will contain between 1 and 30 elements, inclusive.
-All elements of S will be distinct.
-Each element of S will be between -1,000,000 and 1,000,000, inclusive.
-p will be between 1 and 1,000, inclusive.

### Examples

0)

 `{-1,0,1,2,3}` `10`
`Returns: 120`
 All permutations of numbers are valid, so we have 5! = 120 sequences.
1)

 `{6,2}` `4`
`Returns: 0`
 Both numbers have the same remainder modulo 4 and so we cannot create a valid 4-sequence from them.
2)

 `{1,2,3,4}` `3`
`Returns: 12`
3)

 `{4,6,8,-3,7}` `2`
`Returns: 12`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13518&pm=8785

rasto6sk

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming, Recursion