거래

$1$부터 $N$까지의 정수로 표시되는 $N$개 마을이 존재한다. 마을 $1$부터 $N$까지 순서대로 이동하면서 단일 품목(한 종류)의 물건에 대해 거래를 하려고 한다.

각 마을에서는 "물건을 $1$개 사기" 또는 "원하는 만큼 $0$개 이상 물건을 팔기"를 선택할 수 있다. 물론, 시작 시에는 물건을 가지고 있지 않다.

마을 $i$에서 한 개의 물건을 사거나 파는 가격은 동일하고 이 가격을 $P_i$라고 하자. 몇 개의 마을에서는 물건의 가격이 알려져 있지만, 그 외의 마을에서는 가격이 알려져 있지 않다. 그러나, $N$개의 가격 $P_1, \cdots, P_N$은 항상 $\{1, 2, \cdots, N\}$의 순열임은 알려져 있다.

가격을 나타내는 순열 $P_1, \cdots, P_N$을 $[ P_1, \cdots, P_N ]$으로 표기하자. 여기서, 이미 알려진 가격을 제외하고 $?$(물음표)로 표시하면, 알려지지 않은 가격들에 대하여 모든 가능한 순열을 나타낼 수 있다. 예를 들어, 이미 알려진 가격 $2$와 $1$에 대해, $[ ?, 2, ?, 1 ]$은 순열 $[ 3, 2, 4, 1 ]$과 $[ 4, 2, 3, 1 ]$을 나타낸다.

물건의 가격을 나타내는 $?$가 포함된 순열이 주어질 때, 가능한 모든 순열 각각에 대해서, 사고 파는 거래를 통해서 얻을 수 있는 최대 이득을 구하고 그 총합을 출력하는 프로그램을 작성하시오.

예를 들어, $[ 1, ?, 3, ? ]$이 주어지면, 순열 $[ 1, 2, 3, 4 ]$에서는 마을 $1$, $2$, $3$에서 각각 물건을 사고 마을 $4$에서 물건을 모두 팔아 $6$의 이득을 얻는다. 또한 순열 $[ 1, 4, 3, 2 ]$에서는 마을 $1$에서 물건을 사고 마을 $2$에서 팔아 $3$의 이득을 볼 수 있다. 따라서, 최대 이득의 총합은 $6 + 3 = 9$이다.

입력 형식

첫 줄에 마을의 개수를 나타내는 정수 $N$이 주어진다. $(2 \le N \le 8\,000)$

그다음 줄에 마을의 물건 가격의 순열을 나타내는 $N$개 정수 $P_1, \cdots, P_N$이 공백으로 구분되어 차례대로 주어진다. 여기서, $1$ 이상 $N$ 이하의 정수는 이미 알려진 물건 가격을 나타내고, $0$은 물건 가격이 알려지지 않은 $?$임을 나타낸다. 양수인 $P_i$의 값은 모두 다르다.

출력 형식

첫 줄에 모든 가능한 순열에 대한 최대 이득의 총합을 $998\,244\,353$으로 나눈 나머지를 출력한다.

예제 1

4
1 0 3 0

9

예제 2

4
1 4 3 2

3

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설