G-Avoiding Sequence

Time limit1sMemory limit128 MB

Summary

Count permutations of a set where consecutive elements never differ by a multiple of G, modulo a prime.

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

Problem

You are given a set $S$ of distinct integers and an integer $G$ . A sequence of integers is called a G-Avoiding Sequence if both of the following conditions hold:

the sequence is a permutation of the elements of $S$ ; and
for any two consecutive elements $A$ and $B$ in the sequence, $A - B$ is not divisible by $G$ .

Compute the number of G-Avoiding Sequences modulo the prime 1,234,567,891.

Input

The input consists of several test cases. The first line of each test case contains two integers $N$ ( $1 \le N \le 200$ ), the size of $S$ , and $G$ ( $1 \le G \le 1000$ ). The next line contains $N$ integers, the elements of $S$ , each between $0$ and $10^6$ .

The input ends with a single line containing $N = G = 0$ , which must not be processed.

Output

For each test case, output a single line containing the number of G-Avoiding Sequences modulo 1,234,567,891.

Examples3

Example 1
Input
```
4 3
1 2 3 4
3 100
10 110 42
0 0
```
Expected output
```
12
2
```
Example 2
Input
```
1 5
7
0 0
```
Expected output
```
1
```
Example 3
Input
```
2 3
1 2
0 0
```
Expected output
```
2
```