题目描述

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 \le 10$；

对于 $30\%$ 的数据有 $n \le 1000,m \le 1000$；

对于 $100\%$ 的数据保证 $n \le 500000, m \le 500000, 1≤k≤n,q≤10^{18},1≤a _ i≤10000$。