← 返回题目列表

Codeforces · 272/D

D. 迪马和两个序列

中文机器翻译题面 查看原题

Little Dima 有两个具有整数坐标的点序列:序列 (a1, 1), (a2, 2), ..., (an, n) 和序列 (b1, 1), (b2, 2), ..., (bn, n)。

现在Dima想要计算可以从这些序列组装的长度为2·n的不同点序列的数量,使得组装序列中点的x坐标不会减少。帮助他。请注意,初始序列的每个元素应在组装序列中仅使用一次。

Dima 认为两个组装序列 (p1, q1), (p2, q2), ..., (p2·n, q2·n) 和 (x1, y1), (x2, y2), ..., (x2·n, y2·n) 不同,如果存在这样的 i (1 ≤ i ≤ 2·n),则 (pi, qi) ≠ (xi, yi)。

由于答案可能相当大,因此打印答案除以数字 m 所得的余数。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。第三行包含 n 个整数 b1, b2, ..., bn (1 ≤ bi ≤ 109)。行中的数字由空格分隔。

最后一行包含整数 m (2 ≤ m ≤ 109 + 7)。

输出

在单行中打印问题答案除以数字 m 后的余数。

示例

输入 #1

1
1
2
7

输出 #1

1

输入 #2

2
1 2
2 3
11

输出 #2

2

注意

在第一个示例中,您只能获得一个序列:(1, 1), (2, 1)。

在第二个示例中,您可以获得这样的序列: (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2)。因此,答案是2。