P-Sequences

Time limit2sMemory limit256 MB

Summary

Count permutations of a set of distinct integers where no two adjacent elements have a difference divisible by P, for two test cases, modulo 1234567891.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

A sequence S of distinct integers is given. A permutation T made by using every element of S exactly once is called a P-sequence of S if it satisfies the following condition.

T contains every element of S exactly once.
For every two adjacent elements in T, their difference must not be divisible by P.

Compute the number of P-sequences of S.

Input

The input consists of two test cases. Each test case has two lines. The first line contains the number of elements N in S and the integer P. N is a positive integer no greater than 30, and P is a positive integer no greater than 1,000. The second line contains the N distinct elements of S. Each element is between -1,000,000 and 1,000,000, inclusive.

Output

For each test case, in input order, output one line containing the number of P-sequences of S modulo 1234567891.

Examples3

Example 1
Input
```
5 10
-1 0 1 2 3
2 1000
1 -1
```
Expected output
```
120
2
```
Example 2
Input
```
2 4
6 2
4 3
1 2 3 4
```
Expected output
```
0
12
```
Example 3
Input
```
5 2
4 6 8 -3 7
5 3
4 6 8 -3 7
```
Expected output
```
12
48
```