G-회피 수열

서로 다른 정수들의 집합 $S$와 정수 $G$가 주어진다. 다음 두 조건을 모두 만족하는 정수 수열을 G-회피 수열(G-Avoiding Sequence)이라고 한다.

1. 수열은 $S$의 모든 원소를 한 번씩 사용한 순열이다.
2. 수열에서 인접한 두 원소 $A$와 $B$에 대해, $A - B$가 $G$로 나누어떨어지지 않는다.

G-회피 수열의 개수를 소수 1,234,567,891로 나눈 나머지를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 집합 $S$의 크기 $N$ ($1 \le N \le 200$)과 정수 $G$ ($1 \le G \le 1000$)이 주어진다. 둘째 줄에는 $S$의 원소인 $N$개의 정수가 주어지며, 각 값은 $0$ 이상 $10^6$ 이하이다.

입력의 마지막에는 $N = G = 0$인 줄이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 G-회피 수열의 개수를 1,234,567,891로 나눈 나머지를 한 줄에 하나씩 출력한다.