1282번 - P-수열

서로 다른 정수로 이루어진 수열 S가 주어진다. 다음과 같은 조건을 만족하는 수열은 S의 P-수열이라고 말한다.

1. S의 원소를 정확하게 하나씩 포함해야 한다.
2. 임의의 인접한 두 원소 S₁, S₂가 있을 때, (S₁-S₂)는 P로 나누어 떨어지지 않아야 한다.

S의 P-수열 개수를 출력하는 프로그램을 작성하시오.

문제는 두 개의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스 첫째 줄에 S의 원소 개수 N과 P가 주어진다. N은 30보다 작거나 같은 자연수이다. P는 1,000보다 작거나 같은 자연수이다. 둘째 줄에 S의 원소 N개가 주어진다. 모든 원소는 서로 다르고, -1,000,000보다 크거나 같고 1,000,000보다 작거나 같다.

한 줄에 하나 씩 입력 받은 순서대로 S의 P-수열 개수를 1234567891로 나눈 나머지를 출력한다.