题目描述

一名徒步旅行者准备翻越一座山。向导只提供了以下信息：山的最大高度、从山脚一侧走到另一侧的水平距离，以及沿途若干地标的高度和它们出现的先后顺序。

整条山路只由以下三种地形组成，并且每一种地形持续的水平长度都是整数米：

• 上升地形：每水平前进 $1$ 米，高度上升 $1$ 米；
• 水平地形：每水平前进 $1$ 米，高度不变；
• 下降地形：每水平前进 $1$ 米，高度下降 $1$ 米。

设整条山路的水平长度为 $D$，最大高度为 $H$。山路从高度 $0$ 开始，并在水平前进恰好 $D$ 米后回到高度 $0$。

给定 $L$ 个地标，其高度依次为 $a_1,a_2,\ldots,a_L$。这些地标在山路上必须按照给定顺序出现，并且任意两个地标所在位置的水平距离至少为 $1$ 米。地标的具体水平坐标并未给出，只要求存在一种放置方式满足这些条件。

一条山路是合法的，当且仅当同时满足：

1. 起点高度为 $0$，终点高度也为 $0$；
2. 除起点和终点外，山路上的任何位置高度都严格大于 $0$；
3. 山路至少有一个位置的高度恰好为 $H$；
4. 山路上的高度从不超过 $H$；
5. 可以在山路上按顺序放置所有给定地标，使第 $i$ 个地标所在位置的高度为 $a_i$，且不同地标之间至少相隔 $1$ 米。

一条山路可以看成长度为 $D$ 的地形序列，每一米分别选择“上升”“水平”或“下降”。如果两条山路在至少一个水平单位区间上的地形类型不同，则认为它们是不同的山路。

请计算合法山路的数量。如果不存在合法山路，输出 $0$。

输入格式

第一行输入三个整数 $L,D,H$，分别表示地标数量、山路的水平长度和山的最大高度。

若 $L>0$，第二行输入 $L$ 个整数 $a_1,a_2,\ldots,a_L$，按地标在山路上出现的顺序给出它们的高度；若 $L=0$，则不存在地标数据。

输出格式

输出一个整数，表示满足所有条件的合法山路数量。

保证答案不超过 $2^{63}-1$。

数据范围与约定

• $2\le D\le100$；
• $1\le H\le50$；
• $0\le L\le50$；
• $1\le a_i\le H$；
• 答案不超过 $2^{63}-1$。

输入输出样例 #1

输入

0 5 2

输出

3

输入输出样例 #2

输入

0 2 45

输出

0

输入输出样例 #3

输入

2 5 2
2 2

输出

1

输入输出样例 #4

输入

4 8 3
2 2 3 1

输出

7

样例说明

对于样例 #1，水平长度为 $5$、最大高度为 $2$，且没有地标限制，共有 $3$ 条合法山路。互为镜像的两条山路仍被视为不同方案。

对于样例 #3，两个地标的高度都为 $2$。由于两个地标不能放在同一个位置，因此只有能够在两个不同水平位置依次经过高度 $2$ 的山路才可能合法，最终只有 $1$ 种方案。