Sau khi học xong lesson DP on Trees của __BruteForce__, chupe hkbao cảm thấy rất hứng thú với dạng toán này nên đã nghiền ngẫm các bài toán suốt một đêm.

Bỗng Bảo nghĩ ra một bài toán khá đơn giản nhưng thú vị liền mang lên lớp đố nqtrieu, bài toán phát biểu như sau: Cho \(N\) số nguyên không âm \(d_1,\ d_2,\ldots,\ d_N\), hỏi có bao nhiêu cách dựng cây thỏa mãn khoảng cách từ đỉnh \(1\) đến đỉnh thứ \(i\) đúng bằng \(d_i\), \(\forall i\in [1,N]\). Biết rằng các cạnh trên cây đều có trọng số là \(1\). Nhưng Triệu lại đang bận tương tư TTT nên không còn tâm trí nghĩ cách giải bài này, các bạn hãy giúp cậu ấy nhé!

Nhắc lại: cây là đồ thị vô hướng, liên thông và không có chu trình.

Vì kết quả có thể rất lớn nên chỉ cần lấy phần dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\);
• Dòng tiếp theo chứa \(N\) số nguyên dương \(d_1,\ d_2,\ldots,\ d_N\).

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Ràng buộc

• \(1\leq N\leq 10^5\);
• \(0\leq d_i\leq N-1,\ \forall i\in [1,N]\).

Ví dụ

Sample input 1

4
0 1 1 2

Sample output 1

2

Sample input 2

4
1 2 2 3

Sample output 2

0