USCOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs Web Board
Login Register

1455: 上楼

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：81 Solved：17
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

在不断地攀爬 $10^5$ 数量级的楼梯后。小明攀爬的大楼终于装上了电梯。
但是十分不幸，不是所有楼层都开了电梯。
我们视大楼为 $n$ 层。其中 $m$ 层可以停靠电梯。
小明在任意楼层可以向上窜 $1$ 层或 $2$ 层。
在第 $a_{i}(1\le i < m)$ 层，他可以乘坐电梯，并选择到达第 $a_{j}(i<j \le m)$ 层。
小明一开始位于大楼下(第 $0$ 层)，他想知道这次能有多少种方案到达第 $n$ 层。
答案可能很大，请输出答案对 $998244353$ 取模后的答案。

Input

第一行，包含两个整数 $n,m$ ,依次代表总楼层数与可停靠电梯的楼层数。
第二行，包含 $m$ 个严格单调递增的整数。第 $i$ 个整数 $a_i$ 表示第 $a_i$ 层可以停靠电梯。




数据范围:
$1 \le m \le n \le 10^5$
$1 \le a_{i} \le n$

Output

一个整数，代表到达第 $n$ 层的方案数。

Sample Input Copy 

4 3
1 2 3

Sample Output Copy 

11

HINT

样例中共11种方案


$0 \underset{楼梯}{\rightarrow} 1 \underset{楼梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{楼梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{楼梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{电梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{楼梯}{\rightarrow} 2 \underset{电梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{电梯}{\rightarrow} 2 \underset{电梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{电梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 1 \underset{电梯}{\rightarrow} 2 \underset{楼梯}{\rightarrow} 4$

$0 \underset{楼梯}{\rightarrow} 2 \underset{电梯}{\rightarrow} 3 \underset{楼梯}{\rightarrow} 4$




Source/Category