테니스

Little MP는 가족, 친구와 함께 테니스 대회를 보는 것을 좋아한다. 최근 TV로 Australian Open 2022 결승을 보았는데, 선수들이 쓰는 테니스공마다 0부터 $w - 1$까지의 정수 무게가 있어야 한다는 것을 알게 되었다. 같은 무게라도 공의 모델은 여러 가지일 수 있다. 무게 $i$에 대해 이 무게를 가진 서로 다른 모델이 $v\_i$개 있다.1 무게와 모델이 같은 두 공은 서로 같은 것으로 본다.

Little MP는 고향의 단골 스포츠 용품점 InfO(1)Sports에 갔다가, 지난달 TV에서 본 테니스공 모델이 모두 무한히 공급되는 것을 확인한다. 즉, 무게 $i$마다 그 무게를 가진 $v\_i$개 모델의 공이 각각 무한히 있다.

Little MP는 테니스공 $n$개를 사려고 하는데 조건이 있다. 무게가 $w\_1, \dots, w\_n$이고 모델이 $m\_1, \dots, m\_n$인 공을 순서대로 샀다고 하자. 그러면 $(w\_1 + \dots + w\_n) \mod w ≤ x$를 만족해야 한다.

이 가게는 가격을 특이하게 정한다. 공 $n$개로 이루어진 열의 가격은 $count^k$이며, 여기서 $count$는 열에서 무게가 $y$ 이하인 공의 개수이다.

Little MP는 다음이 궁금하다. 조건을 만족하는 길이 $n$의 공 열을 모두 생각할 때, 그 비용의 합은 얼마인가? 같은 공이 여러 번 들어가도 되고 순서가 중요하다. 예를 들어 $(w, m)$을 무게 $w$, 모델 $m$인 공이라고 하면, 열 $(1, 2), (2, 1)$은 $(2, 1), (1, 2)$와 다르다. 두 열은 모든 자리에 같은 공이 있을 때만 같은 열로 본다.

1 대회에서 $v\_i = 0$이면 무게 $i$의 공은 사용되지 않았다고 약속한다.

첫 줄에 정수 $n$, $w$, $k$, $x$, $y$가 주어진다. 둘째 줄에는 각 무게의 서로 다른 모델 수인 $v\_0, v\_1, \dots, v\_{w-1}$이 주어진다.

조건을 만족하는 모든 공 열의 비용 합을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

• $1 ≤ n ≤ 10^9$
• $1 ≤ w ≤ 700$
• $0 ≤ v\_0, v\_1, \dots, v\_{w-1} ≤ 10^9$
• $1 ≤ k ≤ 2$
• $0 ≤ x, y < w$

무게 $w$, 모델 $m$인 공을 $(w, m)$으로 나타낸다.

처음 두 예제에는 공이 전혀 없다. 따라서 살 수 있는 열이 없고 비용의 합은 $0$이다.

셋째와 넷째 예제에서 공은 $(0, 1)$, $(0, 2)$, $(1, 1)$, $(1, 2)$이다. Little MP는 $(0, 1)$, $(0, 2)$, $(1, 1)$, $(1, 2)$ 중 하나를 살 수 있다. 두 예제 모두 각 열의 비용은 $1$이다($1^1 = 1^2 = 1$). 따라서 합은 $4$이다.

다섯째 예제에서도 공은 같고, Little MP는 공 두 개를 어떤 조합으로든 살 수 있다. 따라서 $4 \times 4 = 16$개의 열이 있다. 두 개짜리 열의 비용은 무게가 $1$ 이하인 공의 개수($n = 2$개 모두)의 $k = 1$제곱이므로 $2$이다. 비용의 합은 $32$이다.

다음 예제에서 공은 $(0, 1)$, $(1, 1)$, $(2, 1)$의 세 가지이다. Little MP는 $3$으로 나눈 나머지가 $1$ 이하가 되는 무게의 공을 하나 살 수 있으므로 $(0, 1)$ 또는 $(1, 1)$을 살 수 있다. 두 열의 비용은 모두 $1$이므로 합은 $2$이다.