Given a positive integer $ n $ and a sequence $ lim_0, lim_1, lim_2, \dots, lim_n $ of length $ n+1 $, find the number of integer sequences $ f_0, f_1, f_2, \dots, f_n $ of length $ n+1 $ such that the following conditions hold:
- For all $ 0 \le i \le n $, $ 0 \le f_i \le lim_i $.
- For any $ 0 \le m \le n $, for all $ 0 \le i \le m $, $ f_{f_i+f_{m-i}} = f_m $ holds. (If $ i > n $, $ f_i = -1 $)
The answer should be taken modulo $ 998244353 $.
Input
The input consists of two lines.
The first line contains a positive integer $ n $, representing the length of the sequence as $ n+1 $.
The second line contains $ n+1 $ positive integers, representing $ lim_0, lim_1, \dots, lim_n $ respectively.
Output
Output a single integer representing the number of sequences satisfying the requirements, modulo $ 998244353 $.
Examples
Input 1
2 2 2 2
Output 1
6
Note 1
The valid sequences are: [0,0,0],[0,1,0],[0,1,1],[0,1,2],[1,0,1],[1,1,1].
Input 2
5 1 1 4 5 1 4
Output 2
8
Input 3
10 0 1 2 3 4 5 6 7 8 9 10
Output 3
56
Constraints
The sample files in Unix format are provided in the download.
For $ 100\% $ of the data, $ 1 \le n \le 2000, 0 \le lim_i \le n $.
There are $ 20 $ test cases in total. The constraints for each test case are as follows:
| Test Case Number | $ n \le $ | Other Constraints |
|---|---|---|
| $ 1 $ | $ 1 $ | None |
| $ 2 $ | $ 5 $ | None |
| $ 3 $ | $ 15 $ | None |
| $ 4 $ | $ 30 $ | None |
| $ 5 $ | $ 50 $ | None |
| $ 6 $ | $ 70 $ | None |
| $ 7 $ | $ 100 $ | None |
| $ 8 $ | $ 200 $ | None |
| $ 9 $ | $ 100 $ | $ lim_0=0 $ |
| $ 10 $ | $ 500 $ | $ lim_0=0 $ |
| $ 11 $ | $ 2000 $ | $ lim_0=0 $ |
| $ 12 $ | $ 2000 $ | $ lim_0=0 $ and $ lim_i \le 5 $ |
| $ 13 $ | $ 2000 $ | $ lim_i \le 5 $ |
| $ 14 $ | $ 2000 $ | $ lim_i \le 20 $ |
| $ 15 \sim 16 $ | $ 2000 $ | $ lim_i=i $ |
| $ 17 \sim 20 $ | $ 2000 $ | None |