Пройдя все трудности и невзгоды, Саша наконец решил жениться на своей девушке. Для этого нужно подарить ей обручальное кольцо. Однако его девушке не нравятся подобные романтические жесты, но нравятся бинарные деревья поиска\(^{\dagger}\). Поэтому Саша решил ей подарить такое дерево.
Проведя немало времени на свадебных сайтах для программистов, он нашел идеальное бинарное дерево поиска с корнем в вершине \(1\). В нём значение в вершине \(v\) равно \(val_v\).
Но спустя некоторое время он забыл значения в некоторых вершинах. Пытаясь вспомнить найденное дерево, Саша задался вопросом — сколько существует бинарных деревьев поиска, которые он мог найти на сайте, если известно, что значения во всех вершинах являются целыми числами и принадлежат отрезку \([1, C]\). Поскольку это число может быть очень большим, выведите его по модулю \(998\,244\,353\).
\(^{\dagger}\)Бинарным деревом поиска называется корневое бинарное дерево, у которого для любой вершины \(x\) выполняется свойство: значения всех вершин в левом поддереве вершины \(x\) (если оно существует) меньше или равны значению в вершине \(x\) и значения всех вершин в правом поддереве вершины \(x\) (если оно существует) больше или равны значению в вершине \(x\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — количество подходящих бинарных деревьев поиска по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных, бинарное дерево поиска имеет следующий вид:
Тогда возможными значениями в вершинах являются: \([2, 2, 3, 2, 2]\), \([2, 2, 3, 2, 3]\), \([2, 2, 3, 3, 3]\) и \([3, 2, 3, 3, 3]\).
Во втором наборе входных данных значения во всех вершинах известны, поэтому существует единственное подходящее бинарное дерево поиска.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 5
2 3 -1
-1 -1 2
4 -1 3
-1 5 -1
-1 -1 -1
3 69
2 3 47
-1 -1 13
-1 -1 69
3 3
2 3 -1
-1 -1 -1
-1 -1 -1
|
4
1
10
|