nodgd在做题的时候，发现某道题的答案可以通过一个简单的公式算出来：

其中 \(x_1,x_2,\dots,x_n\) 都是输入数据当中给出的，$y$是这道题的答案。

当nodgd辛辛苦苦写完程序交上去的时候，发现这道题居然没有数据！内心充满正义的nodgd决定立刻生成一些数据，以防恶意提交；但这个数据又不能太简单，如果数据太简单就会让一些奇怪的程序能够通过。nodgd希望造出一些数据，满足以下条件：

1. \(x_1,x_2,\dots,x_n\) 都是非负整数，且不超过$2^m-1$；
2. 输入的前 \(k\) 个数 \(x_1,x_2,\dots,x_k\) 要交给nodgd全权负责，nodgd会给出这 \(k\) 个数的值；
3. 公式计算的结果 \(y​\) 不超过nodgd的身高，即给定正整数 \(h​\) ，计算结果满足 \(y \leq h​\) 。

nodgd当然知道如何生成数据，但是他想知道一共可以生成多少种不同的数据。只要两组数据的某个位置上的数不同就认为这两组数据不同，例如 \(n=3\) 时， \(\\{x_1,x_2,x_3\\}\) 为 \(\\{1,2,3\\},\\{1,2,4\\},\\{3,2,1\\}\) 都是不同的数据。答案可能很大，所以只需要 \(\bmod\ 1,000,000,007\) 后的结果。

输入共两行。

第一行包含 $4$ 个整数 \(n,m,k,h\) ，含义如问题描述中所述。

第二行 \(k\) 个数，表示nodgd钦定的数值，也就是的 \(x_1,x_2,\dots,x_k\) 的值。

输出共一行。

输出一行，一个整数，表示满足条件的不同的数据有多少种， \(\bmod\ 1,000,000,007\) 后的值。

输入输出样例1说明

公式是

要满足每个数都不超过 $2^m-1=22-1=3$ ，且 \(x_1=3,y\leq1\) 的条件。

可以通过枚举得到所有符合条件的 $12$ 组数据：

数据规模与约定

前 $10\%$ 的数据， \(n=4,\ m=2,\ k=0\) ；

前 $30\%$ 的数据， \(n\leq 15,\ m=2\) ；

前 $60\%$ 的数据， \(n\leq 15,\ m\leq 60\) ；

全部测试数据， $1\leq n\leq1000,\ 1\leq m\leq 60,\ 0\leq k\leq n,\ 0\leq h,x_1,x_2,\dots,x_k\leq 2^m-1$ 。