406782: GYM102538 H Horrible Cycles
Description
You are given a bipartite graph with $$$n$$$ vertices in each part.
In this graph, each vertex from the left part is connected to some prefix of vertices from the right part. Namely, the $$$i$$$-th vertex in the left part is connected with vertices $$$1, 2, \ldots, a_i$$$ in the right part.
Find the number of vertex-simple cycles in this graph. Two cycles are different if there exists some edge which is present in one cycle but not in the other.
As this number may be large, find it modulo $$$998\,244\,353$$$.
InputThe first line of input contains one integer $$$n$$$ ($$$1 \leq n \leq 5000$$$): the number of vertices in each part.
The next line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$): a description of the given graph.
OutputOutput one integer: the number of vertex-simple cycles in the given graph, modulo $$$998\,244\,353$$$.
ExamplesInput1 1Output
0Input
2 2 2Output
1Input
3 3 3 2Output
7Input
10 6 6 7 7 8 8 9 9 10 10Output
410150080