Hard: P-Sequence

Hard: P-Sequence

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

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)2006, TopCoder, Inc. All rights reserved.