#P3554. [Shoi2014]神秘金字塔
[Shoi2014]神秘金字塔
[SHOI2014] 神秘金字塔
题目描述
考古学家在 CCM 文明遗迹中发现了一座残缺的金字塔。他们已知它由相同的 石块垒成,并满足以下条件。
- 每一层的石块在俯视平面内形成一个连通块。除底层之外,每一块石块都由正下方一层的石块支撑。
- 每层的俯视形状都左右对称、上下对称,且各层对应的对称轴重合。从任一对称轴向两侧考察,长度或宽度均不增加。
- 每层的最大长度和最大宽度相等,且为偶数。
给定石块总数、金字塔总层数及从底到顶的每层最大长度,求满足条件的不同金字塔形状数。各层的形状和叠放位置由俯视格子上的石块高度确定。
输入格式
第一行两个整数 ,表示石块总数和金字塔层数。接下来 行,每行一个整数 ,表示从底往上第 层的最大长度,该层的最大宽度也为 。保证 单调不增。
输出格式
一行一个整数,表示满足条件的形状数对 取模后的结果。
样例 #1
36 3
6
4
2
1
样例 #2
44 2
6
4
3
下图从上到下展示样例一的唯一形状和样例二的三个形状。每格数字表示该处堆叠的石块数,空白格没有石块。

数据范围
| 原赛累计分值 | 条件 |
|---|---|
| ,, | |
| ,, | |
| ,, |