UOJ Logo

NOI.AC

1S 512MB

#1631. RPG之旅

Statistics

题目描述

backlight最近迷上了RPG游戏,一天他在玩一个很经典的单线剧情RPG,游戏可以简化为一条长度为无限的道路,道路被划分为一个个均匀的小格,可以看作编号为1开始依次增大,每个格子的状态为空或者存在怪物,由于这个游戏看似是个RPG游戏,但是本质上是个逃生游戏,所以其实他走到怪物所在的格子便会死亡,所以他必须小心的绕过怪物,但可悲的是,在这个游戏里,他只能选择前进一步或两步,另外由于backlight有高超的技巧,所以当他经过怪物所在的格子而非停在那里时,他将平安无事,一开始,backlight在编号为1的格子上,请问他有多少种方案安全走过这一片怪物区域?

文件输入

输入第一行为一个整数 n 
之后一行为n个数,第i个数为ai,分别为n只怪物的所在位置

文件输出

输出一个正整数,表示安全走过怪物区域的方案数,由于答案较大,需要对1000 000 007取模

输入样例

2 
2 4

输出样例

1

数据规模

对于10%的数据,n=0
对于10%的数据,n=1
对于10%的数据,存在相邻的两只怪物
对于前50%的数据,ai<=1000
对于前70%的数据,ai<=1000000
对于100%的数据,ai<=100000000,n<=10

样例解释

一开始在格点1处,可以选择转移到2或者3,2处死亡,3处可以选择前进到4或者5,共有1种方案