\(n\) человек участвуют в голосовании. У каждого человека есть ровно один голос.
\(i\)-й человек состоит в команде \(t_i\) (\(1 \leq t_i \leq n\)), где \(t_i = t_j\) означает что \(i\), \(j\) состоят в одной команде. По правилам человек может проголосовать только за человека из другой команды. Обратите внимание, что это автоматически означает, что каждый человек не может проголосовать за себя.
Каждый человек знает количество голосов \(c_i\), которое он хочет получить. Сколько существует возможных способов провести голосование, так что каждый человек получит желаемое количество голосов? Поскольку это число может быть очень большим, найдите его по модулю \(998\,244\,353\).
Выходные данные
Выведите единственное целое число — количество способов провести голосование по модулю \(998\,244\,353\).
Примечание
В первом тесте есть два возможных способа провести голосование: \((2, 3, 1)\), \((3, 1, 2)\).
В третьем тесте есть пять возможных способов провести голосование: \((3, 3, 2, 2, 1)\), \((2, 3, 2, 3, 1)\), \((3, 3, 1, 2, 2)\), \((3, 1, 2, 3, 2)\), \((2, 3, 1, 3, 2)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 1
1 2 3
|
2
|
|
2
|
5
2 0 1 0 2
1 2 3 4 5
|
10
|
|
3
|
5
1 2 2 0 0
3 5 4 3 4
|
5
|