G-회피 수열

시간 제한1초메모리 제한128 MB

요약

집합의 순열 중에서 인접한 두 원소의 차가 G의 배수가 되지 않는 순열의 개수를 소수로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

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

수열은 $S$ 의 모든 원소를 한 번씩 사용한 순열이다.
수열에서 인접한 두 원소 $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로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
4 3
1 2 3 4
3 100
10 110 42
0 0
```
예상 출력
```
12
2
```
예제 2
입력
```
1 5
7
0 0
```
예상 출력
```
1
```
예제 3
입력
```
2 3
1 2
0 0
```
예상 출력
```
2
```