题目描述

Dr.Orange 正在进行动物心理学研究，其中一项研究需要根据动物的进食习惯推断生态系统中每种动物的数量。已知该生态系统中共有 $n$ 种动物，第 $i$ 种动物每次进食会消耗 $a_i$ 份饵料。Dr.Orange 的实验持续了 $m$ 天，第 $i$ 天投入了 $t_i$ 份饵料，且每天的饵料均被全部消耗完毕。在这 $m$ 天中的每一天，不同的动物依次轮流进食饵料。你需要回答每天存在多少种不同的进食序列。两个序列相同当且仅当序列每个位置上的动物种类均相同。由于结果可能非常庞大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 与 $m$（$1\le n,m\le 100$）。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$（$1\le a_i\le 100$）。

第三行包含 $m$ 个整数，依次表示第 $i$ 天投入的饵料份数 $t_i$（$1\le t_i\le 10^9$）。

输出格式

输出一行包含 $m$ 个整数，其中第 $i$ 个整数表示第 $i$ 天的答案对 $10^9+7$ 取模后的结果。

5 3
5 4 4 2 3
5 8 3

3
16
1

10 5
9 1 6 5 10 4 9 2 7 6
64 92 43 30 2

566507809
840913760
608266829
85862862
2

提示

对于第一个样例中的第一天，共有三种可能的进食序列：$[1]$、$[4,5]$ 以及 $[5,4]$。序列中的数字表示动物的种类。

翻译由 DeepSeek V3.2 完成