P5148 Big Loop

hke learned loop statements one day and found them amazing. Back home, he wrote the following code in C++: ```cpp void work() { ans=0; for(a[1]=1;a[1]

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$.

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

- 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