이상적인 울타리

정원에 $n$개의 줄기로 이루어진 울타리가 있다. 이 줄기는 식물인 아이비이며 Puljka가 아니다. $i$번째 줄기의 높이는 $A_i$이고, 모든 줄기 높이의 합은 $S$이다.

울타리를 다듬기 위해 Malnar 씨는 정한 높이에서 줄기를 자른다. 줄기는 쉽게 부러지므로 각 줄기는 최대 한 번만 자를 수 있다. Malnar 씨는 가위질에 능숙하지 않아서, 줄기 하나를 높이 $v$에서 자르면 이웃한 줄기 중 높이가 $v$보다 엄격히 큰 줄기도 같은 높이 $v$에서 잘라야 한다. 모든 줄기를 자를 필요는 없다. 가위를 잊고 왔다면 한 줄기도 자르지 않는다.

그림 I.1 왼쪽은 올바른 자르기이고 오른쪽은 잘못된 자르기이다. 2번째와 3번째 열 사이, 4번째와 5번째 열 사이에서 자르는 것은 허용되지 않는다.

$0$부터 $S$까지의 길이 $X$마다, Malnar 씨는 울타리를 잘라서 전체 길이가 $X$가 되는 방법이 몇 가지인지 알고 싶어 한다. 어떤 줄기의 높이라도 다르면 서로 다른 울타리이다. 정확한 개수 대신 $998\,244\,353$으로 나눈 나머지를 구한다.

첫 줄에 줄기의 수 $n$ ($1 \le n \le 2\,000$)이 주어진다. 둘째 줄에는 $n$개의 정수가 주어지며, $i$번째 수는 $i$번째 줄기의 높이 $A_i$ ($0 \le A_i \le 2\,000$)이다. 모든 높이의 합 $S$는 $2\,000$ 이하이다.

$S + 1$개의 줄을 출력한다. $i$번째 줄에는 전체 높이의 합이 $i - 1$인 울타리의 가능한 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 예제에서 전체 길이가 $1$인 울타리는 만들 수 없다. 3번째 줄기를 높이 $0$에서 자르면 4번째 줄기도 높이 $0$에서 잘라야 하고, 반대로 4번째 줄기를 자르면 3번째 줄기도 잘라야 하기 때문이다. 전체 길이가 $2$부터 $7$까지인 각 경우에는 정확히 한 가지 방법이 있다. 길이 $2$부터 $6$까지는 4번째 열을 잘라서 만들고, 길이 $7$은 아무것도 자르지 않아서 만든다. 전체 길이가 $0$인 울타리는 모든 줄기를 높이 $0$에서 자르면 만들어진다.