题目描述

给定一个长为 $N$ 的非负整数序列 $A$，满足 $0 \leq A_i < i$。问有多少个 $1 \sim N$ 的排列 $P$ 满足：$\forall i \in [1,N]$，对于 $A_i < j < i$ 有 $P_j > P_i$，如果 $A_i > 0$ 有 $P_{A_i} < P_i$。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数，表示序列 $A$。

输出格式

一行一个整数表示答案。

样例

4
0 1 0 3

3

22
0 1 2 2 2 2 2 2 1 9 9 9 9 0 14 15 15 15 14 19 19 19

353820794

样例解释

满足第一组样例输入数据的三个排列为 $(2,3,1,4),(2,4,1,3),(3,4,1,2)$。

数据范围

$10\%$ 的数据满足 $N \leq 10$

$0 \leq A_i < i$，$1 \leq N \leq 10^6$。

输入数据保证至少存在一个排列满足题目给出的条件。