Horrible Cycles

각 왼쪽 정점이 오른쪽 정점의 접두사에 연결된 이분 그래프에서 단순 사이클의 개수를 998244353으로 나눈 나머지로 구한다.

어려움8조합론동적 계획법정렬아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제4

문제

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, . . . , ai 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.

입력

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

The next line of input contains n integers a1, a2, . . . , an (1 ≤ ai ≤ n): a description of the given graph.

출력

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