У Cirno есть ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. В графе ровно одна вершина, не имеющая исходящих ребер. На \(i\)-й вершине написано целое число \(a_i\).
Каждую секунду происходит следующее:
- Пусть \(S\) — множество вершин \(x\), у которых \(a_x > 0\).
- Для всех \(x \in S\) из \(a_x\) вычитается \(1\), а затем для каждой вершины \(y\) такой, что существует ребро из \(x\) в \(y\), \(1\) прибавляется к \(a_y\).
Найдите первый момент времени, когда все \(a_i\) станут равны \(0\). Так как ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите целое число — первый момент времени, когда все \(a_i\) станут \(0\), по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных:
- В момент времени \(0\) значения узлов равны \([1, 1, 1]\).
- В момент времени \(1\) значения узлов равны \([0, 1, 1]\).
- В момент времени \(2\) значения узлов равны \([0, 0, 1]\).
- В момент времени \(3\) значения узлов равны \([0, 0, 0]\).
Так что ответ равен
\(3\).
Во втором наборе входных данных:
- В момент времени \(0\) значения узлов равны \([1, 0, 0, 0, 0]\).
- В момент времени \(1\) значения узлов равны \([0, 1, 0, 0, 1]\).
- В момент времени \(2\) значения узлов равны \([0, 0, 1, 0, 0]\).
- В момент времени \(3\) значения узлов равны \([0, 0, 0, 1, 0]\).
- В момент времени \(4\) значения узлов равны \([0, 0, 0, 0, 1]\).
- В момент времени \(5\) значения узлов равны \([0, 0, 0, 0, 0]\).
Итак, ответ равен
\(5\).
В третьем наборе входных данных:
Первый момент времени, когда все \(a_i\) становятся \(0\), равен \(6\cdot 998244353 + 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2
1 1 1
1 2
2 3
5 5
1 0 0 0 0
1 2
2 3
3 4
4 5
1 5
10 11
998244353 0 0 0 998244353 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
7 9
5 6
1293 1145 9961 9961 1919
1 2
2 3
3 4
5 4
1 4
2 4
6 9
10 10 10 10 10 10
1 2
1 3
2 3
4 3
6 3
3 5
6 5
6 1
6 2
|
3
5
4
28010
110
|