Напомним, что перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Последовательность \(a\) является подотрезком \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца. Обозначим подотрезок как \([l, r]\), где \(l, r\) — целые числа и \(1 \le l \le r \le n\). Это обозначает подотрезок, у которого убрали \(l-1\) элементов слева и \(n-r\) справа.
Для перестановки \(p_1, p_2, \ldots, p_n\) назовём рамочным подотрезком такой подотрезок индексов \([l,r]\), в котором \(\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l\). Например, у перестановки \((6, 7, 1, 8, 5, 3, 2, 4)\) некоторые из рамочных подотрезков: \([1, 2], [5, 8], [6, 7], [3, 3], [8, 8]\). В частности, подотрезок \([i,i]\) всегда является рамочным подотрезком для любого \(i\) от \(1\) до \(n\) включительно.
Для перестановки \(p\) определим счастье перестановки как количество таких пар \((l, r)\), что \(1 \le l \le r \le n\) и \([l, r]\) является рамочным подотрезком. Например, перестановка \([3, 1, 2]\) имеет счастье \(5\): Все подотрезки индексов кроме \([1, 2]\) являются рамочными.
Даны два целых числа \(n\) и \(m\). Джонгвон хочет найти суммарное счастье всех перестановок длины \(n\) по модулю простого числа \(m\). Обратите внимание, что всего существует \(n!\) (факториал \(n\)) различных перестановок длины \(n\).