Вас наняли руководить разработкой проекта нового парка аттракционов. В парке будет некоторая изюминка: от одного аттракциона к другому посетителей будут доставлять специальные направленные спуски.
Владелец парка передал вам текущий проект: список планируемых к постройке аттракционов и список спусков, которые должны быть построены. Так как он предприниматель, то он, как обычно, вообразил невозможное: кроме всего прочего, он запланировал спуск от замка с привидениями к американским горкам, спуск от американских горок к башни свободного падения, а также спуск от башни свободного падения к замку с привидениями. Так как спуски могут вести только вниз, очевидно, что это невозможно. У вас нет привилегий игнорировать законы физики при постройке парка, поэтому в проект нужно внести изменения. Может, владелец примет изменение направления спуска между башней и замком?
Формально:
- Проектом называется список аттракционов и список направленных спусков. Каждый спуск начинается около одного аттракциона и заканчивается у другого.
- Предложение получается из проекта изменением направлений некоторых спусков (возможно, ни одного или всех).
- Предложение корректно, если существует способ выбрать высоты расположений всех аттракционов так, чтобы все спуски вели вниз.
- Стоимостью предложения называется количество спусков, направление которых нужно изменить.
Для данного проекта найдите сумму стоимостей всех корректных предложений по модулю \(998,244,353\).
Выходные данные
Выведите одно целое число — сумму стоимостей всех корректных предложений по модулю \(998,244,353\).
Система оценки
Подзадача 1 (7 баллов): \(n \leq 3\)
Подзадача 2 (12 баллов): \(n \leq 6\)
Подзадача 3 (23 балла): \(n \leq 10\)
Подзадача 4 (21 балл): \(n \leq 15\)
Подзадача 5 (37 баллов): нет дополнительных ограничений
Примечание
В первом примере есть два предложения:
- Направление спуска не изменено. Стоимость \(0\).
- Направление спуска изменено. Стоимость \(1\).
Так как оба предложения корректны, то ответ равен
\(0 + 1 = 1\).
Во втором примере есть восемь предложений, где спуски направлены так:
- \(1 \rightarrow 2\), \(2 \rightarrow 3\), \(1 \rightarrow 3\) (стоимость \(0\))
- \(1 \rightarrow 2\), \(2 \rightarrow 3\), \(3 \rightarrow 1\) (стоимость \(1\))
- \(1 \rightarrow 2\), \(3 \rightarrow 2\), \(1 \rightarrow 3\) (стоимость \(1\))
- \(1 \rightarrow 2\), \(3 \rightarrow 2\), \(3 \rightarrow 1\) (стоимость \(2\))
- \(2 \rightarrow 1\), \(2 \rightarrow 3\), \(1 \rightarrow 3\) (стоимость \(1\))
- \(2 \rightarrow 1\), \(2 \rightarrow 3\), \(3 \rightarrow 1\) (стоимость \(2\))
- \(2 \rightarrow 1\), \(3 \rightarrow 2\), \(1 \rightarrow 3\) (стоимость \(2\))
- \(2 \rightarrow 1\), \(3 \rightarrow 2\), \(3 \rightarrow 1\) (стоимость \(3\))
Второе предложение некорректно, так как есть последовательность спусков \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1\). Это означает, что аттракцион \(1\) должен быть строго выше чем он сам, что, очевидно, невозможно. Аналогично, седьмое предложение тоже некорректно. Поэтому ответ равен \(0 + 1 + 2 + 1 + 2 + 3 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 2
|
1
|
|
2
|
3 3
1 2
2 3
1 3
|
9
|