Сегодня финал INOI (Иранская национальная олимпиада по информатике). Зал для контеста представляет собой ряд из \(n\) компьютеров. Все компьютеры пронумерованы целыми числами от \(1\) до \(n\) слева направо. Всего будет \(m\) участников, пронумерованных целыми числами от \(1\) до \(m\).
У нас есть массив \(a\) длины \(m\), где \(a_{i}\) (\(1 \leq a_i \leq n\)) — это компьютер, около которого \(i\)-й участник хочет сесть.
Также у нас есть другой массив \(b\) длины \(m\), состоящий из символов «L» и «R». \(b_i\) — это сторона, с которой \(i\)-й участник заходит в зал. «L» обозначает, что участник заходит в зал левее \(1\)-го компьютера, и идет слева направо, а «R» обозначает, что участник заходит в зал правее \(n\)-го компьютера, и идет справа налево.
Участники в порядке от \(1\) до \(m\) заходят в зал один за другим. \(i\)-й из них заходит в зал со стороны \(b_i\) и идет до компьютера \(a_i\). Если этот компьютер уже занят, он продолжает идти в том же направлении до первого не занятого компьютера. После этого он садится за этот компьютер. Если участник не встречает ни одного свободного компьютера, он расстраивается и покидает соревнование.
Расстроенность \(i\)-о участника — это расстояние между его желаемым компьютером (\(a_i\)) и компьютером, за который он в итоге сел. Расстояние между компьютерами \(i\) и \(j\) равно \(|i - j|\).
Числа в массиве \(a\) могут быть равны. Существует \(n^m \cdot 2^m\) возможных пар массивов \((a, b)\).
Рассмотрим все пары массивов \((a, b)\) такие, что ни один участник не расстроится. Для каждой из них посчитаем сумму расстроенностей всех участников. Найдите сумму этих чисел.
Вам будет дан некоторый простой модуль \(p\). Найдите эту сумму по модулю \(p\).
Примечание
В первом тесте есть три возможных массива \(a\): \(\{1\}\), \(\{2\}\) и \( \{3\}\) и два возможных массива \(b\): \(\{\mathtt{L}\}\) и \(\{\mathtt{R}\}\). Для всех шести возможных пар массивов \((a, b)\) единственный участник сядет за компьютером \(a_1\) (потому что он точно окажется не занят), поэтому его расстроенность будет равна \(0\). Поэтому сумма всех расстоенностей будет равна \(0\).
Во втором тесте все возможные пары массивов \((a, b)\) такие, что ни один участник не будет расстроен:
- \((\{1, 1\}, \{\mathtt{L}, \mathtt{L}\})\), сумма расстроенностей \(1\);
- \((\{1, 1\}, \{\mathtt{R}, \mathtt{L}\})\), сумма расстроенностей \(1\);
- \((\{2, 2\}, \{\mathtt{R}, \mathtt{R}\})\), сумма расстроенностей \(1\);
- \((\{2, 2\}, \{\mathtt{L}, \mathtt{R}\})\), сумма расстроенностей \(1\);
- все возможные пары массивов \(a \in \{\{1, 2\}, \{2, 1\}\}\) и \(b \in \{\{\mathtt{L}, \mathtt{L}\}, \{\mathtt{R}, \mathtt{L}\}, \{\mathtt{L}, \mathtt{R}\}, \{\mathtt{R}, \mathtt{R}\}\}\), сумма расстроенностей \(0\).
Поэтому ответ равен \(1 + 1 + 1 + 1 + 0 \ldots = 4\).