Yet Another Problem On a Subsequence
The sequence of integers $$$a_1, a_2, \dots, a_k$$$ is called a good array if $$$a_1 = k - 1$$$ and $$$a_1 > 0$$$. For example, the sequences $$$[3, -1, 44, 0], [1, -99]$$$ are good arrays, and the sequences $$$[3, 7, 8], [2, 5, 4, 1], [0]$$$ — are not.A sequence of integers is called good if it can be divided into a positive number of good arrays. Each good array should be a subsegment of sequence and each element of the sequence should belong to exactly one array. For example, the sequences $$$[2, -3, 0, 1, 4]$$$, $$$[1, 2, 3, -3, -9, 4]$$$ are good, and the sequences $$$[2, -3, 0, 1]$$$, $$$[1, 2, 3, -3 -9, 4, 1]$$$ — are not.For a given sequence of numbers, count the number of its subsequences that are good sequences, and print the number of such subsequences modulo 998244353.
In the first test case, two good subsequences — $$$[a_1, a_2, a_3]$$$ and $$$[a_2, a_3]$$$.In the second test case, seven good subsequences — $$$[a_1, a_2, a_3, a_4], [a_1, a_2], [a_1, a_3], [a_1, a_4], [a_2, a_3], [a_2, a_4]$$$ and $$$[a_3, a_4]$$$.
The first line contains the number $$$n~(1 \le n \le 10^3)$$$ — the length of the initial sequence. The following line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(-10^9 \le a_i \le 10^9)$$$ — the sequence itself.
In the single line output one integer — the number of subsequences of the original sequence that are good sequences, taken modulo 998244353.
from sys import stdin, stdout
get_string = lambda : stdin.readline().strip('\n')
get_intmap = lambda : map(int, get_string().split(' '))

def ncr_generator(n, r):
    ncrr = 1
    while True:
        yield ncrr
        n += 1
        ncrr = ncrr * n // (n - r)

def testcase():
    n = int(input())
    a = tuple(get_intmap())
    m = 998244353
    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(n - 1, -1, -1):
        ai = a[i]
        if ai <= 0:
            continue
        for (j, ncrr) in zip(range(i + ai + 1, n + 1), ncr_generator(ai, ai)):
            dp[i] = (dp[i] + ncrr * dp[j]) % m
    ans = 0
    for i in dp[:-1]:
        ans = (ans + i) % m
    print(ans)
testcase()
n = int(input())
m = 998244353
dp = [1] + [0] * n
for i in map(int, input().split()):
    v = dp[:]
    if 0 < i < n:
        v[i] = (v[i] + v[0]) % m
    for j in range(n):
        v[j] = (v[j] + dp[j + 1]) % m
    dp = v
print((dp[0] - 1) % m)
n = int(input())
m = 998244353
dp = [1] + [0] * n
for j in map(int, input().split()):
    v = dp[:]
    if 0 < j < n:
        v[j] = (v[j] + v[0]) % m
    for k in range(n):
        v[k] = (v[k] + dp[k + 1]) % m
    dp = v
print((dp[0] - 1) % m)