К сожалению, Дора пролила краску, когда рисовала мурал в классе. Дора рассматривает мурал как матрицу \(b\) размера \(n \times n\). Изначально \(b_{i,j} = 0\) для всех \(1 \le i, j \le n\).
У Доры есть только две кисти, которые имеют два разных цвета. За одну операцию она может покрасить матрицу одной из двух кистей:
- Первая кисть имеет цвет \(1\) и может покрасить один столбец матрицы. То есть, Дора выбирает целое число \(1 \leq j \leq n\) и присваивает \(b_{i,j} := 1\) для всех \(1 \leq i \leq n\);
- Вторая кисть имеет цвет \(2\) и может покрасить одну строку матрицы. То есть, Дора выбирает целое число \(1 \leq i \leq n\) и присваивает \(b_{i,j} := 2\) для всех \(1 \leq j \leq n\).
Дора раскрашивает матрицу так, чтобы полученная матрица \(b\) содержала только \(1\) и \(2\).
Для матрицы \(b\) обозначим \(f(b)\) как минимальное количество операций, необходимых, чтобы превратить начальную матрицу (содержащую только \(0\)) в \(b\). Красота матрицы \(b\) равна количеству способов раскрасить начальную матрицу за ровно \(f(b)\) операций, чтобы превратить её в \(b\). Если нет способа превратить начальную матрицу в \(b\), то красота \(b\) равна \(0\).
Однако Дора сделала случайную ошибку. В матрице \(a\), которую вы получили, ровно один элемент отличается от настоящей матрицы \(b\). То есть, существует ровно одна пара \((i, j)\) такая, что \(a_{i, j} = 3 - b_{i, j}\).
Пожалуйста, помогите Доре вычислить ожидаемую красоту настоящей матрицы \(b\) по модулю \(998\,244\,353\) (все возможные \(n^2\) ошибок имеют равную вероятность).
Поскольку размер матрицы слишком велик, Дора скажет вам только позиции \(m\) элементов цвета \(1\), а остальные \(n^2-m\) элементов имеют цвет \(2\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — ожидаемую красоту настоящей матрицы \(b\), по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных матрица \(a = \left[\begin{matrix}1&1\\2&2\end{matrix}\right]\). Рассмотрим изменение элемента \((1,1)\) для вычисления ответа.
Можно доказать, что минимальное количество операций для раскрашивания начальной матрицы в \(\left[\begin{matrix}2&1\\2&2\end{matrix}\right]\) равно \(3\). Сначала мы можем покрасить первую строку в цвет \(2\), затем покрасить второй столбец в цвет \(1\), и наконец покрасить вторую строку в цвет \(2\). Процесс выглядит следующим образом:
\(\)\left[\begin{matrix}0&0\\0&0\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&2\\0&0\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&1\\0&1\end{matrix}\right]\Rightarrow\left[\begin{matrix}2&1\\2&2\end{matrix}\right]\(\)
Можно доказать, что это единственный способ раскрасить матрицу за \(3\) операции. Таким образом, красота матрицы \(\left[\begin{matrix}2&1\\2&2\end{matrix}\right]\) равна \(1\). Аналогично, если изменить любой другой элемент матрицы, красота всегда равна \(1\), поэтому ожидаемая красота настоящей матрицы \(b\) равна \(1\).
Во втором наборе входных данных матрица \(a = \left[\begin{matrix}1&2\\2&2\end{matrix}\right]\). Рассмотрим изменение элемента \((2, 2)\) для вычисления ответа.
Можно доказать, что невозможно раскрасить начальную матрицу в \(\left[\begin{matrix}1&2\\2&1\end{matrix}\right]\), поэтому её красота равна \(0\). Если изменить любой другой элемент матрицы, красота всегда равна \(2\), поэтому ожидаемая красота равна \(\frac{0 + 2 + 2 + 2}{4} = \frac{6}{4} \equiv 499\,122\,178 \pmod {998\,244\,353}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 2
1 1
1 2
2 1
1 1
3 2
1 1
3 3
6 0
5 10
1 1
1 2
1 3
2 1
2 3
5 1
5 2
5 3
5 4
5 5
3 5
1 1
1 3
2 2
3 1
3 3
4 3
1 1
2 3
2 4
|
1
499122178
665496236
120
79859554
776412275
1
|