题目描述

小 Z 在梦中获得灵感：已知收银员要找给小 Z 的金额 $N$、钱柜里的硬币种类 $K$ 以及 $K$ 种硬币的面额，计算有多少种不同的找零方法？

这里的“不同”是指所找零钱至少有一种硬币的数量不相同。假设现在只有 $2$ 种硬币，一种面额是 $5$ 分，另一种面额是 $1$ 分，要找给小 Z 的金额是 $8$ 分钱，可以给小 Z 找 $1$ 个五分硬币加 $3$ 个一分硬币，或者找 $8$ 个一分硬币。用 $3$ 个一分硬币加 $1$ 个五分硬币本质上与 $1$ 个五分硬币加 $3$ 个一分硬币没有任何区别，因此只可以用两种不同的方式找出八分钱。

现在给定要找的金额和硬币种类，请你编程计算找零方案的数目。

输入格式

第一行包含两个用空格隔开的整数 $N$ 和 $K$，其中 $1 \le N \le 300$，表示超市收银员要找给小 Z 的金额（单位：分）；$1 \le K \le 8$，表示钱柜里不同面额硬币的种类数。

接下来 $K$ 行每行包含一个正整数 $C_i$（$1 \le C_i \le 100$），表示一种硬币的面额，硬币面额按从大到小的降序排列。不同种类的硬币面额各不相同，每种硬币都取之不尽用之不竭。

输出格式

输出仅一行包含一个整数，表示可能的找零方案数。答案保证不会超出长整型范围。需要注意的是如果没有面额为 $1$ 分的硬币，有些金额将无法找零，此时结果就输出 $0$。

样例

83 5
50
25
10
5
1

159

样例解释
收银员要找给小 Z 金额 $83$ 分，共有 $5$ 种硬币，面额分别为 $50, 25, 10, 5, 1$。共有 $159$ 种不同的找零方案。

数据范围

• $1 \le N \le 300$，$1 \le K \le 8$，$1 \le C_i \le 100$。
• 答案保证在 long long 范围内。