序列(sequence)

题目描述

有$N$个数$a_1..a_n$和一个整数$P$。 将这$N$个数排成一排，并且相邻的两个如果是$a_i$和$a_j$，那么$a_i-a_j$不能是$P$的倍数。 求排成一排的方案数。 保证数据不相同。

输入格式

第一行两个正整数$N$,$P$。 接下来一行为这$n$个数。

输出格式

输出一个数，为对$1234567891$取模的答案。

输入样例

5 10
-1 0 1 2 3

输出样例

120

数据规模和约定

对于20%的数据$1 \le N \le 10$。

对于50%的数据 1 <= N <= 16。

对于100%的数据1 <= N <= 30，-10^6<=ai<=10^6，1<=P<=1000。