Description

hke learned loop statements one day and found them amazing. Back home, he wrote the following code in 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;
}

Here, $q$ is a given constant, and $f(x)$ is a degree $m$ polynomial in $x$, whose expression is:

$$f(x) = a _ m x ^ m + a _ {m - 1} x ^ {m - 1} + \cdots + a _ 1 x + a _ 0$$

hke could not wait to run this program, but it was far too slow. So he came to you and wanted to know what the program outputs. The answer can be very large; you only need to output it modulo $10^9+7$. Assume there is no overflow during the computation.

Input Format

The first line contains 4 positive integers $n, m, k, q$.

The second line contains $m + 1$ positive integers, namely $a_0, a_1, a_2 \cdots a_m$.

Output Format

A single integer, representing the program’s result modulo $10^9+7$.

10 3 3 2
1 3 3 1

3240

Hint

• For $10\%$ of the testdata, $n \le 10$.
• For $30\%$ of the testdata, $n \le 1000, m \le 1000$.
• For $100\%$ of the testdata, it is guaranteed that $n \le 500000, m \le 500000, 1 \le k \le n, q \le 10^{18}, 1 \le a_i \le 10000$.

Translated by ChatGPT 5