该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

半仙有 $m$ 种括号和一个长度为 $n$ 的括号序列，求括号放置使得这个括号序列合法的方案数。

但是半仙认为这个问题太简单了，于是他给你了 $n$ 个限制 $a_1\sim a_n$：若在位置 $i$ 若放右括号，则只能放第 $1\sim a_i$ 种右括号（可以放任何左括号）。

合法括号序列的定义：

• 空序列是合法的；
• 若 $\text A$ 和 $\text B$ 都是合法的序列，则 $\text{AB}$ 也是合法的；
• 若 $\text A$ 是合法的序列，则 $(_i\text A)_i$（即以第 $i$ 种括号成对包围 $\text A$）也是合法的。

输入格式

第一行三个整数 $n,m,D$。

接下来一行 $n$ 个整数 $a_i$。

输出格式

一行一个整数，表示答案，对 $D$ 取模。

4 1 10000
1 1 1 1

2

样例解释1

有以下 2 种方案：()() (())

4 5 10000
0 5 5 5

50

输入 / 输出数据 3，4，5

3.in，3.out，4.in，4.out，5.in，5.out

数据范围

对于全部数据，$1\le n\le10^4,1\le a_i\le m\le10^9\le D\le2\times10^9,0\le a_i\le m$。

一共有 $20$ 个测试点。

对于 $10\%$ 的数据，$n\le10,m=1$；

对于 $30\%$ 的数据，$n\le30$；

对于 $80\%$ 的数据，$n\le300$；

对于编号为奇数的测试点，$a_i=m,D=10^9+7$。