题目描述

我们的大朋友很喜欢计算机科学，而且尤其喜欢多叉树。对于一棵带有正整数点权的有根多叉树，如果它满足这样的性质，我们的大朋友就会将其称作神犇的：点权为 $1$ 的结点是叶子结点；对于任一点权大于 $1$ 的结点 $u$，$u$ 的孩子数目 $deg_u$ 属于集合 $D$，且 $u$ 的点权等于这些孩子结点的点权之和。 给出一个整数 $s$，你能求出根节点权值为 $s$ 的神犇多叉树的个数吗？请参照样例以更好的理解什么样的两棵多叉树会被视为不同的。 我们只需要知道答案关于 $950009857$（$453\times 2^{21}+1$，一个质数）取模后的值。

输入格式

第一行有 $2$ 个整数 $s,m$。 第二行有 $m$ 个互异的整数，$d_1,d_2,\cdots.d_m$，为集合 $D$ 中的元素。

输出格式

输出一行仅一个整数，表示答案模 $950009857$ 的值。

4 2
2 3

10

数据规模与约定

$1\le m<s\le 10^5, 2\le d_i\le s$，有 $3$ 组小数据和 $3$ 组大数据。

题目来源

By Jcvb