大循环

hke 有一天学会了循环语句，感到很神奇。回到家，他用 C++ 写下这段代码： ```cpp 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$ 次多项式，它的表达式为： $$f(x) = a _ m x ^ m + a _ {m - 1} x ^ {m - 1} + \cdots + a _ 1 x + a _ 0$$ 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$。