#P17934. Divide Polygon
Divide Polygon
Divide Polygon
给定正整数 和含 个整数的集合 。
在顶点依次编号为 的正 边形内,画出 条不同的对角线,要求任意两条对角线除端点外不相交。它们将原多边形分成 个多边形。
如果每个得到的多边形的边数都属于 ,则这种画法合法。两个画法不同,当且仅当所选的对角线集合不同;顶点有编号,旋转或翻转不视为同一种画法。
对于每个 ,求合法画法数对 取模的结果。
输入格式
N M
S_1 S_2 ... S_M
输出格式
输出 行。第 行回答 时的答案。
数据范围
,,。所有输入均为整数。
样例 1
输入:
5 2
3 4
输出:
0
5
5
样例 2
输入:
4 1
4
输出:
1
0
样例 3
输入:
16 7
3 4 6 7 9 12 16
输出:
1
24
544
14280
120156
829464
3372120
10914816
24515700
40532624
52300160
42493880
17383860
2674440