AT_abc263_e [ABC263E] Sugoroku 3

题目描述

一共有 $N$ 个格子编号 $1$ 到 $N$。有一个人站在 $1$ 号格子。

对于 $\forall i \in [1,N-1]$ 号格子有一个 $A_i + 1$ 面的骰子，写有 $0$ 到 $A_i$ 这些数。如果 ta 掷到了 $k$，他将往前走 $k$ 格，走到 $i+k$ 号方格。

求走到 $N$ 号方格的期望次数。对 $998244353$ 取模。

输入格式

第一行一个正整数 $N$，第二行 $N-1$ 个正整数表示 $A_i$。

输出格式

如果期望次数为 $\frac{P}{Q}$，输入最小非负整数 $R$ 使得 $R\times Q \equiv P\pmod {998244353}$。

样例 1

输入

3
1 1

输出

4

样例 2

输入

5
3 1 2 1

输出

332748122

说明/提示

$2\leq N\leq 2\times 10^5$

$\forall i \in [1,N-1],1\leq A_i\leq N-i$