题目描述

hke有一天学会了循环语句，感到很神奇。回到家，他用c++写下这段代码：

void work()
{
  ans=0;
    for(a[1]=1;a[1]<=n;++a[1])
      for(a[2]=1;a[2]<a[1];++a[2])
        for(a[3]=1;a[3]<a[2];++a[3])
          //......
            for(a[k]=1;a[k]<a[k-1];++a[k])
              ans+=f(q);
 cout<<ans;
}

其中，$q$是给定的常数，$f(x)$是一个关于$x$的$m$次多项式，它的表达式为：

hke迫不及待地开始运行这个程序，但程序运行得实在太慢了。于是他找到了你，想知道这段程序输出的结果是？答案可能很大，你只需输出其对$10^9+7$取模的结果即可。假设运算过程中不存在溢出。

输入格式

第一行4个正整数，分别为$n,m,k,q$；

第二行m+1个正整数，分别为$a_0,a_1,a_2\cdots a_m$；

输出格式

一个数，表示程序运行结果对$10^9+7$取模的结果。

10 3 3 2
1 3 3 1

3240

提示

10%的数据有n≤10；

30%的数据有n≤1000，m≤1000；

100%的数据保证n≤500000，m≤500000，1≤k≤n，q≤10^18，1≤bi≤10000。