CF272D.Dima and Two Sequences

Little Dima has two sequences of points with integer coordinates: sequence (_a_1, 1), (_a_2, 2), ..., (a__n, n) and sequence (_b_1, 1), (_b_2, 2), ..., (b__n, n).

Now Dima wants to count the number of distinct sequences of points of length 2·n that can be assembled from these sequences, such that the x-coordinates of points in the assembled sequence will not decrease. Help him with that. Note that each element of the initial sequences should be used exactly once in the assembled sequence.

Dima considers two assembled sequences (_p_1, _q_1), (_p_2, _q_2), ..., (_p_2·n, _q_2·n) and (_x_1, _y_1), (_x_2, _y_2), ..., (_x_2·n, _y_2·n) distinct, if there is such i (1 ≤ i ≤ 2·n), that (p__i, q__i) ≠ (x__i, y__i).

As the answer can be rather large, print the remainder from dividing the answer by number m.

小迪马有两组具有整数坐标的点序列：第一组为 $(a_1, 1),\ (a_2, 2),\ \dots,\ (a_n, n)$，第二组为 $(b_1, 1),\ (b_2, 2),\ \dots,\ (b_n, n)$。

现在迪马希望计算：从这两组序列中各取全部 $n$ 个点（即共 $2n$ 个点），拼接成一个长度为 $2n$ 的点序列，使得该序列中各点的 $x$ 坐标不递减（即非严格单调递增）的方案总数。请你帮他解决这个问题。注意：初始两组序列中的每个点都必须且仅能使用一次。

迪马认为两个拼接得到的序列 $(p_1, q_1),\ (p_2, q_2),\ \dots,\ (p_{2n}, q_{2n})$ 与 $(x_1, y_1),\ (x_2, y_2),\ \dots,\ (x_{2n}, y_{2n})$ 是不同的，当且仅当存在某个下标 $i$（$1 \le i \le 2n$），使得 $(p_i, q_i) \ne (x_i, y_i)$。

由于答案可能非常大，请输出答案对给定正整数 $m$ 取模的结果。

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109). The third line contains n integers _b_1, _b_2, ..., b__n (1 ≤ b__i ≤ 109). The numbers in the lines are separated by spaces.

The last line contains integer m (2 ≤ m ≤ 109 + 7).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。
第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$1 \leq a_i \leq 10^9$）。
第三行包含 $n$ 个整数 $b_1,\,b_2,\,...,\,b_n$（$1 \leq b_i \leq 10^9$）。
每行中的数字以空格分隔。

最后一行包含一个整数 $m$（$2 \leq m \leq 10^9 + 7$）。

In the single line print the remainder after dividing the answer to the problem by number m.

在单行中输出该问题答案对数 $m$ 取模后的余数。

In the first sample you can get only one sequence: (1, 1), (2, 1).

In the second sample you can get such sequences : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Thus, the answer is 2.

在第一个样例中，你只能得到一个序列：$(1,\,1),\,(2,\,1)$。

在第二个样例中，你可以得到如下序列：$(1,\,1),\,(2,\,2),\,(2,\,1),\,(3,\,2)$；$(1,\,1),\,(2,\,1),\,(2,\,2),\,(3,\,2)$。因此，答案是 $2$。