#1041. 1-05A. JM的GG之路

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Akatsuki

题目描述

昨天的觉醒之路似乎很多人都走不过,那就不能觉醒了,只能GG了。JM为你量身打造了GG之路。

这个路就很好走了,他是一个 阶的台阶,每阶的编号为 ,初始你就站在 号台阶上。每一步你有 种不同的步长可以走。现在你需要求出,你有多少种不同的走法可以走到 号台阶上。每种步长都没有使用次数的限制。

因为方案数可能很多,你需要输出答案对 取模。

输入格式

第一行两个正整数 ,表示台阶数和可选的步长种类数。

接下来一行 个正整数,表示你可选的步长有哪些。保证所有的步长互不相同。

输出格式

输出一行一个非负整数表示答案。

样例

样例输入1

3 1
1

样例输出1

1

样例输入2

3 2
1 2

样例输出2

2

数据范围与提示