Nested Loop Summation Using Polynomial Evaluation

hke learned the magic of loops and implemented the following nested loop 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 the function f(x) is defined by an m-th degree polynomial:

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

The nested loops iterate over all sequences (a[1], a[2], \dots, a[k]) such that $$1 \leq a[k] < a[k-1] < \cdots < a[2] < a[1] \leq n,$$ which means the number of iterations is the number of ways to choose k distinct numbers from n in descending order, i.e. \(C(n,k)\). Thus, the summation ans is given by:

$$ ans = C(n,k) \times f(q) \mod (10^9+7). $$

Your task is to output the value of ans modulo \(10^9+7\).

inputFormat

The first line contains four integers n, k, q, and m.

The second line contains m+1 space-separated integers representing the coefficients of the polynomial f(x) in descending order of powers, i.e. \(a_m, a_{m-1}, \dots, a_0\).

It is guaranteed that \(1 \leq k \leq n\) and the answer always fits in a 64-bit integer after modulo operations.

outputFormat

Output a single integer which is the result of \(C(n,k) \times f(q) \mod (10^9+7)\).

sample

5 2 3 2
1 2 1

160