1320: #2188. 「SHOI2014」神秘金字塔

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

对神经组织的进化生物学研究将历史追溯到了人类社会形成之初、一个叫做 CCM 的神秘部落。

考古学证据表明,CCM 一度具有高度繁华的文明。然而 CCM 的历史却似乎在一夜之间神秘地消失了。考古学家近日在大西洋底发掘出了一处 CCM 文明遗迹,有希望能够揭开 CCM 古文明失落之谜。

CCM 遗迹的中央是一座巨大的石质建筑,被考古学家称之为金字塔。金字塔有这样四条性质:

  1. CCM 金字塔由完全相同的 1×1×11 \times 1 \times 11×1×1 单位的立方体石块构成;
  2. CCM 金字塔由若干层组成,每一层的石块从正上方看都在平面上形成一个联通块。高层的石块都有低层的石块在下方作为支撑,不会有石块悬空;
  3. CCM 金字塔的每一层严格都满足左右对称和上下对称,并且所有层的对称轴是重合的,从左右/上下对称轴向两端长度/宽度非严格递减;
  4. CCM 金字塔的每一层的最大长度和最大宽度都相等,并且都是偶数(因为 CCM 人认为偶数代表了好运而奇数则会带来不幸)。

然而,不幸的是,遗迹中的金字塔由于年代过于久远,已经残缺不全,难以辨认全貌。为了尽可能地还原 CCM 金字塔的实际情况,考古学家们通过其他证据估计出了 CCM 金字塔所使用的石块个数、金字塔的高度以及每一层的宽度,他们想请你帮忙计算符合上述性质的可能的金字塔个数。

输入格式

第一行两个整数 n,hn,hn,h,表示 CCM 金字塔的总石块数和 CCM 金字塔的高度。
从第二行开始的 hhh 行,每行一个整数 lll,表示从最底层开始的每一层的最大长度(宽度),保证非严格递减。

输出格式

输出一行一个整数,表示可能的金字塔个数。由于方案数可能数量很大,输出答案为模 100000000710000000071000000007 之后的结果。

样例

样例输入1

36 3 
6 
4 
2

样例输出1

1

样例解释1

样例一的金字塔从顶向下看的样子(数字表示这一格的高度):

    1 1
    2 2
1 2 3 3 2 1
1 2 3 3 2 1
    2 2
    1 1

样例输入2

44 2 
6 
4

样例输出2

3

样例解释2

样例二的金字塔从顶向下看可能的样子(数字表示这一格的高度):

  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

数据范围与提示

对于 100%100\%100% 的数据,n≤1000, 2≤l≤20, 1≤h≤10n \leq 1000,\ 2 \leq l \leq 20,\ 1 \leq h \leq 10n1000, 2l20, 1h10