Horrible Cycles

Time limit2sMemory limit512 MB

Summary

Count the simple cycles in a bipartite graph where each left vertex i connects to the right prefix 1 to a_i, modulo 998244353, with n up to 5000.

Level: Hard8 of 10
Topics: Graph, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

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 that is present in one cycle but not in the other.

As this number may be large, output it modulo $998\,244\,353$ .

Input

The first line contains one integer $n$ ( $1 \le n \le 5000$ ): the number of vertices in each part.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ): a description of the graph.

Output

Output one integer: the number of vertex-simple cycles in the given graph, modulo $998\,244\,353$ .

Examples4

Example 1
Input
```
1
1
```
Expected output
```
0
```
Example 2
Input
```
2
2 2
```
Expected output
```
1
```
Example 3
Input
```
3
3 3 2
```
Expected output
```
7
```
Example 4
Input
```
10
6 6 7 7 8 8 9 9 10 10
```
Expected output
```
410150080
```