У маленького Димы есть две последовательности точек с целочисленными координатами: последовательность (a1, 1), (a2, 2), ..., (an, n) и последовательность (b1, 1), (b2, 2), ..., (bn, n).
Теперь Дима хочет подсчитать сколько различных последовательностей точек длины 2·n можно собрать из этих последовательностей, таких что x-координаты точек в собранной последовательности будут не убывать. Помогите ему в этом. Обратите внимание, что каждый элемент каждой из начальных последовательностей должен быть использован ровно один раз в собранной последовательности.
Две собранные последовательности (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.
Примечание
В первом примере можно получить только одну последовательность: (1, 1), (2, 1).
Во втором примере можно получить такие последовательности : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Таким образом ответ 2.