P-수열

서로 다른 정수로 이루어진 수열 S가 주어진다. S의 모든 원소를 한 번씩 사용해 만든 순열 T가 다음 조건을 만족하면 T를 S의 P-수열이라고 한다.

1. T는 S의 모든 원소를 정확히 한 번씩 포함한다.
2. T에서 서로 이웃한 두 원소의 차이는 P로 나누어떨어지지 않아야 한다.

S의 P-수열이 몇 개인지 구하라.

입력은 두 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에는 S의 원소 개수 N과 정수 P가 주어진다. N은 30 이하의 자연수이고, P는 1,000 이하의 자연수이다. 둘째 줄에는 S의 서로 다른 원소 N개가 주어진다. 각 원소는 -1,000,000 이상 1,000,000 이하이다.

각 테스트 케이스마다 입력 순서대로 한 줄에 하나씩 S의 P-수열 개수를 1234567891로 나눈 나머지를 출력한다.