题目描述

小 Z 整理完房间时间已经不早了，简单洗漱一下就上床睡觉了，自从进入初三后小 Z 已经有很久没有做梦了，不做梦的主要原因是学习强度太大加上睡得较晚，一旦睡着就睡得特别沉，沉到没有梦的地步。今晚小 Z 的大脑皮层特别兴奋，大约是由于白天在 CZ 中学上的课实在太精彩了，这不小 Z 刚睡着就进入了梦乡。在梦里小 Z 梦见自己代表祖国赴 B 国参加了国际信息学奥林匹克竞赛（International Olympiad in Informatics，简称 IOI）并获得了金牌。

颁奖会结束后小 Z 想到附近的超市去买些礼物带回国送给班里的小伙伴们，小 Z 心想 B 国的巧克力代表了爱的愿望、大众的迷恋，是食物中的王者，早在 19 世纪就已经闻名于世了，给小伙伴们每人买一盒巧克力肯定会大受欢迎。于是小 Z 一进超市就直奔装有巧克力的货架，一口气拿了 40 盒 Godiva 巧克力，然后到收银台去排队结帐，轮到小 Z 结账时，他发现自己身上只有一张大面额的 B 国钞票了，于是他把这张钞票递了过去，收银员迅速在收银机上算出了要找给小 Z 的金额，然后打开钱柜准备找钱，小 Z 看到钱柜里的硬币按面额从大到小整整齐齐地摆放着，一种面额的硬币垒成一列，见此情景小 Z 一下就来了灵感，心想少年宫正在为本次活动征集试题呢，就拿这个找零问题考考小朋友们不是挺好吗？小 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$ 种不同面额的硬币。

第 $2$ 到 $K+1$ 行每行包含一个正整数 $C_i$，其中 $1\le C_i\le 100$，表示一种硬币的面额，在输入数据中硬币面额按降序排列（从最大到最小）。

不同种类的硬币面额各不相同，每种硬币都取之不尽用之不竭。

输出格式

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

样例

83 5
50
25
10
5
1

159

数据范围

$10\%$ 的数据：$N\le 50$，$K\le 3$，$C_i\le 10$

$30\%$ 的数据：$N\le 100$，$K\le 5$，$C_i\le 20$

$60\%$ 的数据：$N\le 100$，$K\le 7$，$C_i\le 50$

$100\%$ 的数据：$N\le 300$，$K\le 8$，$C_i\le 100$

来源

市赛