P-Sequences

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.

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

Compute the number of P-sequences of S.

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.

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