P-수열
시간 제한2초메모리 제한256 MB
정수 집합의 원소를 모두 한 번씩 써서 인접한 두 원소의 차가 P의 배수가 되지 않도록 배열하는 순열의 수를 두 테스트케이스에 대해 1234567891로 나눈 나머지로 구합니다.
문제
서로 다른 정수로 이루어진 수열 S가 주어진다. S의 모든 원소를 한 번씩 사용해 만든 순열 T가 다음 조건을 만족하면 T를 S의 P-수열이라고 한다.
- T는 S의 모든 원소를 정확히 한 번씩 포함한다.
- T에서 서로 이웃한 두 원소의 차이는 P로 나누어떨어지지 않아야 한다.
S의 P-수열이 몇 개인지 구하라.
입력
입력은 두 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에는 S의 원소 개수 N과 정수 P가 주어진다. N은 30 이하의 자연수이고, P는 1,000 이하의 자연수이다. 둘째 줄에는 S의 서로 다른 원소 N개가 주어진다. 각 원소는 -1,000,000 이상 1,000,000 이하이다.
출력
각 테스트 케이스마다 입력 순서대로 한 줄에 하나씩 S의 P-수열 개수를 1234567891로 나눈 나머지를 출력한다.