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。