1317: #2188. 「SHOI2014」神秘金字塔
[Creator : ]
Description
对神经组织的进化生物学研究将历史追溯到了人类社会形成之初、一个叫做 CCM 的神秘部落。
考古学证据表明，CCM 一度具有高度繁华的文明。然而 CCM 的历史却似乎在一夜之间神秘地消失了。考古学家近日在大西洋底发掘出了一处 CCM 文明遗迹,有希望能够揭开 CCM 古文明失落之谜。
CCM 遗迹的中央是一座巨大的石质建筑,被考古学家称之为金字塔。金字塔有这样四条性质:
考古学证据表明，CCM 一度具有高度繁华的文明。然而 CCM 的历史却似乎在一夜之间神秘地消失了。考古学家近日在大西洋底发掘出了一处 CCM 文明遗迹,有希望能够揭开 CCM 古文明失落之谜。
CCM 遗迹的中央是一座巨大的石质建筑,被考古学家称之为金字塔。金字塔有这样四条性质:
- CCM 金字塔由完全相同的 $1 \times 1 \times 1$ 单位的立方体石块构成；
- CCM 金字塔由若干层组成，每一层的石块从正上方看都在平面上形成一个联通块。高层的石块都有低层的石块在下方作为支撑，不会有石块悬空；
- CCM 金字塔的每一层严格都满足左右对称和上下对称，并且所有层的对称轴是重合的，从左右/上下对称轴向两端长度/宽度非严格递减；
- CCM 金字塔的每一层的最大长度和最大宽度都相等，并且都是偶数（因为 CCM 人认为偶数代表了好运而奇数则会带来不幸）。
Input
第一行两个整数 n,h，表示 CCM 金字塔的总石块数和 CCM 金字塔的高度。
从第二行开始的 h 行，每行一个整数 l，表示从最底层开始的每一层的最大长度(宽度)，保证非严格递减。
从第二行开始的 h 行，每行一个整数 l，表示从最底层开始的每一层的最大长度(宽度)，保证非严格递减。
Output
输出一行一个整数，表示可能的金字塔个数。由于方案数可能数量很大，输出答案为模 1000000007 之后的结果。
Constraints
对于 $100\%$ 的数据，$n \leq 1000,\ 2 \leq l \leq 20,\ 1 \leq h \leq 10$。
Sample 1 Input
36 3
6
4
2
Sample 1 Output
1
样例一的金字塔从顶向下看的样子（数字表示这一格的高度）：
1 1
2 2
1 2 3 3 2 1
1 2 3 3 2 1
2 2
1 1
Sample 2 Input
44 2
6
4
Sample 2 Output
3
金字塔从顶向下看可能的样子（数字表示这一格的高度）：
1 1 1 1
1 1 2 2 1 1
1 2 2 2 2 1
1 2 2 2 2 1
1 1 2 2 1 1
1 1 1 1
1 1 1 1
2 2 2 2
1 2 2 2 2 1
1 2 2 2 2 1
2 2 2 2
1 1 1 1
1 1
1 2 2 2 2 1
1 2 2 2 2 1
1 2 2 2 2 1
1 2 2 2 2 1
1 1