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.


-----Input-----

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.


-----Output-----

In the single line output one integer — the number of subsequences of the original sequence that are good sequences, taken modulo 998244353.


-----Examples-----
Input
3
2 1 1

Output
2

Input
4
1 1 1 1

Output
7



-----Note-----

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]$.

Difficulty: interview

Starter code:

Solutions:
3

MOD = 998244353

def solve(N, A):
    dp = [[0] * N for _ in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(N):
            c = dp[i][j]

            dp[i + 1][j] += c
            dp[i + 1][j] %= MOD

            if j == 0:
                if A[i] > 0 and A[i] < N:
                    dp[i + 1][A[i]] += c
                    dp[i + 1][A[i]] %= MOD
            else:
                dp[i + 1][j - 1] += c
                dp[i + 1][j - 1] %= MOD

    return (dp[N][0] + MOD - 1) % MOD


def main():
    N = int(input())
    A = [int(e) for e in input().split(' ')]
    assert len(A) == N
    print(solve(N, A))


def __starting_point():
    main()

__starting_point()

from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


MAX = 10000
MOD = 998244353
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX


def COMinit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1;
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    return None


def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


N = read()
A = readlist()

for i in range(N):
    A[i] = max(0, A[i])
    if A[i] > N - i - 1:
        A[i] = 0

COMinit()

dp = [0] * N

for n in range(1, N):
    dp[n] = dp[n-1]
    for i in range(n):
        if i == 0:
            dp[n] = (dp[n] + COM(n - i - 1, A[i] - 1)) % MOD
        else:
            dp[n] = (dp[n] + COM(n - i - 1, A[i] - 1) * (dp[i - 1] + 1)) % MOD

print(dp[N - 1])

mod = 998244353

n = int(input())
a = list(map(int, input().split()))

c = [[1]*n for _ in range(n)]
for i in range(n):
    for j in range(1, i//2 + 1):
        c[i][i-j] = c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod


d = [0] * n + [1]
for i in range(n-1,-1,-1):
    if a[i] <= 0:
        continue
    for j in range(i+a[i]+1,n+1):
        d[i] += (d[j] * c[j-i-1][a[i]])
    d[i] %= mod

print((sum(d)-1)%mod)


MOD = 998244353

n = int(input())
d = [0] * n
a = list(map(int, input().split()))
for i in range(n - 2, -1, -1):
    if (a[i] <= 0):
        continue
    cur_cnk = 1
    cur_k = a[i]
    cur_n = a[i]
    for j in range(i + a[i] + 1, n):
        d[i] = (d[i] + d[j] * cur_cnk % MOD) % MOD
        cur_cnk *= (cur_n + 1)
        cur_cnk //= (cur_n + 1 - cur_k)
        cur_n += 1
    if (i + a[i] + 1 <= n):
        d[i] = (d[i] + cur_cnk) % MOD
ans = 0
for i in range(n):
    ans = (ans + d[i]) % MOD
print(ans)


MOD = 998244353

n = int(input())
d = [0] * n
a = list(map(int, input().split()))
for i in range(n - 2, -1, -1):
    if (a[i] <= 0):
        continue
    cur_cnk = 1
    cur_k = a[i]
    cur_n = a[i]
    for j in range(i + a[i] + 1, n):
        d[i] = (d[i] + d[j] * cur_cnk % MOD) % MOD
        cur_cnk *= (cur_n + 1)
        cur_cnk //= (cur_n + 1 - cur_k)
        cur_n += 1
    if (i + a[i] + 1 <= n):
        d[i] = (d[i] + cur_cnk) % MOD
ans = 0
for i in range(n):
    ans = (ans + d[i]) % MOD
print(ans)

def __starting_point():
    N = int(input())
    a = [0] + list(map(int, input().split()))
    mod = 998244353
    dp = [[0 for i in range(N + 2)] for i in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(N + 1):
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j + 1]) % mod
        if a[i] <= N and a[i] > 0:
            dp[i][a[i]] = (dp[i][a[i]] + dp[i - 1][0] + 1) % mod
    print(dp[N][0])

__starting_point()

m = 998244353
n = int(input())
u = [1] + [0] * n
for a in map(int, input().split()):
    v = u[:]
    if 0 < a < n: v[a] += u[0]
    for j in range(n): v[j] = (v[j] + u[j + 1]) % m
    u = v
print((u[0] - 1) % m)

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 = 1009
MOD = 998244353

a = [0]*N
dp = [0]*N
C = []
for i in range(0,N):
	C.append([0]*N)

for i in range(0,N):
	C[i][0] = 1
	C[i][i] = 1
	for j in range(1,i):
		C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD

n = int(input())
b = input().split()
for i in range(0,n):
	a[i] = int(b[i])

dp[n] = 1
for i in range(n-1,-1,-1):
	if(a[i] <= 0):
		continue
	for j in range(i+a[i]+1, n+1):
		dp[i] += (dp[j]*C[j-i-1][a[i]]) % MOD
		dp[i] %= MOD

soma = 0
for i in range(0,n):
	soma += dp[i]
	soma %= MOD

print(soma)


from random import randint

def factMod(n, mod):
    res = 1
    for i in range(2, n+1):
        res = (res * i) % mod
    return res

def powMod(n, p, mod):
    res = 1

    while p > 0:
        if p % 2 == 1:
            res = (res * n) % mod
        
        p //= 2
        n = (n * n) % mod

    return res

def invMod(n, mod):
    return powMod(n, mod - 2, mod)

#t = 6
#print(invMod(t, 97))
#print( (invMod(t, 97) * t) % 97 )
#return

def CnkMod(n, k, mod):
    return (
        factMod(n, mod) *
        invMod(factMod(k, mod) * factMod(n-k, mod), mod)
    ) % mod

def computeCnksMod(N, mod):
    res = [[0] * (N+1) for i in range(N+1)]
    res[0][0] = 1
    for n in range(1, N+1):
        res[n][0] = res[n-1][0]
        for k in range(1, n+1):
            res[n][k] = (res[n-1][k] + res[n-1][k-1]) % mod

    return res

magic = 998244353

n = int(input()) + 1
aa = [1] + [int(s)+1 for s in input().split(' ')]

#aa = [1] + [randint(0, 999) for i in range(1000)]
#n = len(aa)

cnks = computeCnksMod(n, magic)

#print('aa:', aa)

d = [0] * (n + 1)
d[n] = 1

for i in reversed(list(range(n))):
    if i != 0 and aa[i] < 2:
        continue
    
    cur = 0

    tosel = aa[i] - 1
    for j in range(i + tosel + 1, n + 1):
        avail = j - i - 1
        #cur = (cur + CnkMod(avail, tosel, magic) * d[j]) % magic
        cur = (cur + cnks[avail][tosel] * d[j]) % magic
    
    d[i] = cur

#print(d)
print(d[0] - 1)


def computeCnksMod(N, mod):
    res = [[0] * (N+1) for i in range(N+1)]
    res[0][0] = 1
    for n in range(1, N+1):
        res[n][0] = res[n-1][0]
        for k in range(1, n+1):
            res[n][k] = (res[n-1][k] + res[n-1][k-1]) % mod

    return res

magic = 998244353

n = int(input()) + 1
aa = [1] + [int(s)+1 for s in input().split(' ')]

cnks = computeCnksMod(n, magic)

d = [0] * (n + 1)
d[n] = 1

for i in reversed(list(range(n))):
    if i != 0 and aa[i] < 2:
        continue
    
    cur = 0
    
    tosel = aa[i] - 1
    for j in range(i + tosel + 1, n + 1):
        avail = j - i - 1
        cur = (cur + cnks[avail][tosel] * d[j]) % magic
    
    d[i] = cur

print(d[0] - 1)


def computeCnksMod(N, mod):
    res = [[0] * (N+1) for i in range(N+1)]
    res[0][0] = 1
    for n in range(1, N+1):
        res[n][0] = res[n-1][0]
        for k in range(1, n+1):
            res[n][k] = (res[n-1][k] + res[n-1][k-1]) % mod

    return res

magic = 998244353

n = int(input()) + 1
aa = [1] + [int(s)+1 for s in input().split(' ')]

cnks = computeCnksMod(n, magic)

d = [0] * (n + 1)
d[n] = 1

for i in reversed(list(range(n))):
    if i != 0 and aa[i] < 2:
        continue
    
    cur = 0
    
    tosel = aa[i] - 1
    for j in range(i + tosel + 1, n + 1):
        avail = j - i - 1
        cur = (cur + cnks[avail][tosel] * d[j]) % magic
    
    d[i] = cur

print(d[0] - 1)


n=int(input())
s=list(map(int,input().split()))
mod=998244353
cm=[[0 for i in range(n+2)]for j in range(n+2)]
for i in range(n+2):
    cm[i][0]=1
for i in range(1,n+2):
    for j in range(1,n+2):
        cm[i][j]=cm[i-1][j]+cm[i-1][j-1]
        cm[i][j]=cm[i][j]%mod
dp=[0 for i in range(n+2)]
acum=[0 for i in range(n+2)]
for i in range(n-1,-1,-1):
    acum[i]=acum[i+1]
    if s[i]<=0:
        continue
    for j in range(i+s[i],n):
        dp[i]=(cm[j-(s[i]+i)+s[i]-1][s[i]-1]+cm[j-(s[i]+i)+s[i]-1][s[i]-1]*acum[j+1]+dp[i])%mod
    acum[i]=(dp[i]+acum[i])%mod
print(acum[0])


n = int(input())
arr = list(map(int, input().split()))
mod = 998244353

dp = [0] * (n + 2)
C = [[0] * (n + 2) for i in range(n + 2)]

for i in range(0, n + 1):
    C[i][0] = 1
    for j in range(1, i + 1):
        C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod

ans = 0
dp[n] = 1
for iter in range(0, n):
    i = n - iter - 1
    if arr[i] <= 0:
        continue
    for j in range(i + arr[i] + 1, n + 1):
        dp[i] += dp[j] * C[j - i - 1][arr[i]]
        dp[i] %= mod
    ans += dp[i]

print(ans % mod)

n=int(input())
s=list(map(int,input().split()))
mod=998244353
cm=[[0 for i in range(n+2)]for j in range(n+2)]
for i in range(n+2):
    cm[i][0]=1
for i in range(1,n+2):
    for j in range(1,n+2):
        cm[i][j]=cm[i-1][j]+cm[i-1][j-1]
        cm[i][j]=cm[i][j]%mod
dp=[0 for i in range(n+2)]
acum=[0 for i in range(n+2)]
for i in range(n-1,-1,-1):
    acum[i]=acum[i+1]
    if s[i]<=0:
        continue
    for j in range(i+s[i],n):
        dp[i]=(cm[j-(s[i]+i)+s[i]-1][s[i]-1]+cm[j-(s[i]+i)+s[i]-1][s[i]-1]*acum[j+1]+dp[i])%mod
    acum[i]=(dp[i]+acum[i])%mod
print(acum[0])

#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open('input.txt', 'r')
MOD = 998244353
sys.setrecursionlimit(1000000)

def ncr(n, r):
    nonlocal f
    return f[n]*pow(f[r], MOD-2, MOD)*pow(f[n-r], MOD-2, MOD) % MOD

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
f = [1]
for i in range(1, n+1):
    f.append((f[-1]*i) % MOD)
for i in range(n):
    if i+a[i] < n and a[i] > 0: dp[i] = ncr(n-1-i, a[i])
for i in reversed(range(n)):
    if a[i] <= 0: continue
    for j in range(i+a[i]+1, n):
        dp[i] = (dp[i]+ncr(j-1-i, a[i])*dp[j]) % MOD
print(sum(dp) % MOD)

# https://codeforces.com/problemset/problem/1000/D
# TLE
n   = int(input())
a   = list(map(int, input().split()))
mod = 998244353

def pow_(x, p, mod):
    if p == 1: return x % mod 
    
    tmp  = pow_(x, p // 2, mod)
    if p % 2 == 0:
        return (tmp * tmp) % mod
    else:
        return (tmp * tmp * x) % mod
    
def reverse(x, mod):
    return pow_(x, mod-2, mod)

def create_gt(gt):
    for i in range(2, len(gt)):
        gt[i] = gt[i-1] * i % mod
    
def kCn(k, n, mod):
    return gt[n] * reverse(gt[k], mod) * reverse(gt[n-k], mod) % mod

# C(k, n ) = C(k-1, n-1) + C(k, n-1)
def create_kcn(N, mod):
    kcn       = [[0] * N for _ in range(N)]
    kcn[0][0] = 1
    
    for n in range(1, N):
        for k in range(n, -1, -1):
            kcn[k][n] = ( kcn[k-1][n-1] + kcn[k][n-1] ) % mod  
    return kcn

kcn = create_kcn(1001, mod)
dp = [-1] * n

for i in range(n-2, -1, -1):
    if a[i] > 0 and i + a[i] < n:
        temp = 0
        for j in range(i+a[i]+1, n):
            if dp[j] > 0:
                temp = ( temp + dp[j] * kcn[a[i]][j-i-1] ) % mod
        temp  = (temp + kcn[a[i]][n-i-1]) % mod
        dp[i] = temp

print(sum([x for x in dp if x>0]) % mod)        

#4
#1 1 1 1


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)


m = 998244353
n = int(input())
u = [1] + [0] * n
#purvikaurraina
for a in map(int, input().split()):
    v = u[:]
    if 0 < a < n: v[a] += u[0]
    for j in range(n): v[j] = (v[j] + u[j + 1]) % m
    u = v
print((u[0] - 1) % m)



m = 998244353
n = int(input())
u = [1] + [0] * n
for a in map(int, input().split()):
    v = u[:]
    if 0 < a < n: v[a] += u[0]
    for j in range(n): v[j] = (v[j] + u[j + 1]) % m
    u = v
print((u[0] - 1) % m)



n = int(input())
m = 998244353
dl = [1] + [0] * n;
for i in map(int, input().split()) :
    v = dl[:]
    if(0 < i < n) :
        v[i] = (v[i] + v[0]) % m
    for j in range(n) :
        v[j] = (v[j] + dl[j + 1]) % m
    dl = v
print((dl[0] - 1) % m)


m = 998244353
n = int(input())
u = [1] + [0] * n
for a in map(int, input().split()):
    v = u[:]
    if 0 < a < n: v[a] += u[0]
    for j in range(n): v[j] = (v[j] + u[j + 1]) % m
    u = v
print((u[0] - 1) % m)
r= 6


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)
#print the result