31419번 - 배열 제작의 달인

문제

0ドル$ 이상 $N$ 이하의 정수로 이루어진 길이 $N$의 배열 $A$가 있다.

Jiro는 값이 0ドル$인 모든 원소를 1ドル$ 이상 $N$ 이하의 정수로 바꾸려고 한다. 이때, 바꾼 배열은 아래 조건에 맞아야 한다.

• 1ドル$ 이상 $N$ 이하의 각 정수 $x$에 대하여, 배열 $A$에 $x$가 등장하는 횟수는 $x$ 이하이다.

Jiro가 조건에 맞게 만들 수 있는 배열의 가짓수를 998ドル ,円 244 ,円 353$으로 나눈 나머지를 구하시오. 998ドル,244円,353円$은 소수이다.

입력

첫 번째 줄에 배열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 3,000円)$

두 번째 줄에 배열 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $(0 \leq A_i \leq N)$

출력

첫 번째 줄에 Jiro가 조건에 맞게 만들 수 있는 배열의 가짓수를 998ドル ,円 244 ,円 353$으로 나눈 나머지를 출력한다.

제한

힌트