题目描述

给定一个元素集合$\red S$，求$\red S$的所有排列满足对于任意相邻两个元素$\red {s_1}$,$\red{ s_2}$,($\red{ s_1}$-$\red{ s_2}$)不被$\red P$整除。

保证$\red S$中任意两个元素都不相同。

输入格式

第一行一个数$\red n$，表示集合$\red S$的大小 以下$\red n$个数 最后一个数$\red P$

输出格式

一个数，表述满足条件的排列的个数，模$\red {1234567891}$。

样例

输入样例

4
1 2 3 4
3

输出样例

12

提示

$\red {30\% n<=9}$

$\red {100\% n<=30,S_i<=10^6}$