Определим для массива \(b\) функцию \(f\) такую, что \(f(b)\) возвращает массив префиксных максимумов \(b\). Другими словами, \(f(b)\) — это массив, содержащий только такие элементы \(b_i\), для которых \(b_i=\max(b_1,b_2,\ldots,b_i)\), без изменения их порядка. Например, \(f([3,10,4,10,15,1])=[3,10,10,15]\).
Вам дано дерево, состоящее из \(n\) вершин с корнем \(1\).
Перестановка\(^\dagger\) \(p\) является прямым обходом дерева, если для всех \(i\) выполняется следующее условие:
- Пусть \(k\) — число потомков\(^\ddagger\) вершины \(p_i\).
- Для всех \(x\) таких, что \(i < x \leq i+k\), \(p_x\) — потомок вершины \(p_i\).
Найдите количество различных значений \(f(a)\) среди всех возможных прямых обходов \(a\). Так как это значение может быть большим, вам нужно найти его по модулю \(998\,244\,353\).
\(^\dagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
\(^\ddagger\) Вершина \(t\) является потомком вершины \(s\), если \(s \neq t\) и \(s\) находится на единственном простом пути из \(t\) в \(1\).
Примечание
В первом наборе входных данных единственным допустимым прямым обходом является \(a=[1]\). Поэтому единственное возможное значение \(f(a)\) — \([1]\).
Во втором наборе входных данных единственным допустимым прямым обходом является \(a=[1,2]\). Поэтому единственное возможное значение \(f(a)\) — \([1,2]\).
В третьем наборе входных данных два допустимых прямых обхода — \(a=[1,2,3]\) и \(a=[1,3,2]\). Таким образом, возможные значения \(f(a)\) — \([1,2,3]\) и \([1,3]\).
В пятом наборе входных данных возможными значениями \(f(a)\) являются:
- \([1,5]\);
- \([1,2,5]\);
- \([1,3,5]\);
- \([1,4,5]\);
- \([1,2,3,5]\);
- \([1,2,4,5]\);
- \([1,3,4,5]\);
- \([1,2,3,4,5]\).