题目描述

树老师爬楼梯，他每次可以选择的步数有多种。具体地，有 $m$ 种允许的步长 $a_1, a_2, \dots, a_m$，每次可以选择其中一种步长迈出。给定楼梯的总级数 $N$，请你计算一共有多少种不同的走法可以恰好走完这 $N$ 级台阶。

输入格式

第一行，两个整数 $N$ 和 $m$。
第二行，$m$ 个正整数 $a_1, a_2, \dots, a_m$，表示每次可以走的步长。

输出格式

一行，一个整数，表示不同的走法总数。

样例

5 2
1 2

8

数据范围

• $1 \le N \le 30$
• $1 \le m \le N$
• $1 \le a_i \le N$