题目描述

Little MP 喜欢和家人、朋友一起观看网球比赛。他最近观看了 2022 年澳大利亚网球公开赛决赛，并注意到：比赛中使用的每个网球，其重量都是区间

$$0,1,\ldots,w-1$$

中的一个整数。

对于每种重量，可能存在多个不同型号的网球。重量为 $i$ 的网球共有 $v_i$ 种型号。重量和型号均相同的两个网球被认为是完全相同的。

Little MP 来到家乡的一家体育用品商店 InfO(1)Sports。他发现，商店对每一种网球型号都有无限库存。也就是说，对于重量 $i$ 的每一种型号，都可以购买任意多个网球。

Little MP 想购买恰好 $n$ 个网球。设按顺序购买的网球重量依次为

$$w_1,w_2,\ldots,w_n,$$

对应的型号依次为

$$m_1,m_2,\ldots,m_n.$$

他要求购买序列满足

$$(w_1+w_2+\cdots+w_n)\bmod w\le x.$$

商店采用一种特殊的计价方式。令 $\mathrm{count}$ 表示购买序列中重量不超过 $y$ 的网球数量，则该序列的价格为

$$\mathrm{count}^k.$$

请考虑所有满足要求的长度为 $n$ 的网球序列，求这些序列价格之和。

一个序列中可以出现多个完全相同的网球，并且网球的排列顺序有意义。例如，用 $(w,m)$ 表示一个重量为 $w$、型号为 $m$ 的网球，则序列

$$(1,2),(2,1)$$

与序列

$$(2,1),(1,2)$$

不同。

两个序列相同，当且仅当它们每个位置上的网球重量和型号都分别相同。

---

输入格式

第一行包含五个整数

$$n,w,k,x,y.$$

第二行包含 $w$ 个整数

$$v_0,v_1,\ldots,v_{w-1},$$

其中 $v_i$ 表示重量为 $i$ 的网球型号数量。

---

输出格式

输出一个整数，表示所有满足要求的网球序列的价格总和，对

$$10^9+7$$

取模后的结果。

---

数据范围

$$1\le n\le 10^9,$$ $$1\le w\le 700,$$ $$0\le v_i\le 10^9,$$ $$1\le k\le 2,$$ $$0\le x,y<w.$$

当 $v_i=0$ 时，表示不存在重量为 $i$ 的网球型号。

---

子任务

表中的“无”表示除完整数据范围外，没有额外限制。

子任务	分值	$n$	$w$	$k$	$x$	$y$	其他限制
1	7	$n\le 10^6$	无	无	$x=w-1$	$y=w-1$	无
2		无
3	10				无	无	$v_0=v_1=\cdots=v_{w-1}=0$
4	15	$n\le 50$	$w\le 50$				无
5	4	$n\le 2500$				$y=w-1$
6	5	无					$v_0=v_1=\cdots=v_{w-1}$
7	11	$n\le 2500$	$w\le 50$	$k=1$		无
8	7	无
9	12	$n\le 2500$		$k=2$
10	7	无
11	9		无	$k=1$
12	11			$k=2$

---

样例

样例 1

输入
7 3 2 1 1
0 0 0

输出
0

样例 2

输入
1000000 4 1 2 1
0 0 0 0

输出
0

样例 3

输入
1 2 1 1 1
2 2

输出
4

样例 4

输入
1 2 2 1 1
2 2

输出
4

样例 5

输入
2 2 1 1 1
2 2

输出
32

样例 6

输入
1 3 1 1 1
1 1 1

输出
2

样例 7

输入
3 2 1 1 1
25 37

输出
714984

样例 8

输入
6 5 2 3 2
1 2 6 70 1

输出
227678571

样例 9

输入
6 5 1 2 3
1 6 70 1 4

输出
398503624

样例 10

输入
500 4 1 2 3
10 20 30 40

输出
651382141

样例解释

在前两个样例中，不存在任何可购买的网球，因此不存在合法序列，答案为 $0$。

在样例 3 和样例 4 中，可选网球为

$$(0,1),(0,2),(1,1),(1,2).$$

Little MP 只购买一个网球，共有四种序列。每个序列中的 $\mathrm{count}=1$，无论 $k=1$ 还是 $k=2$，价格都为 $1$，所以答案为 $4$。

在样例 5 中，可以任意选择两个网球，共有

$$4\times 4=16$$

个有序序列。所有网球重量都不超过 $1$，因此每个序列的 $\mathrm{count}=2$。由于 $k=1$，每个序列价格为 $2$，总价为

$$16\times 2=32.$$

在样例 6 中，共有三个可选网球：

$$(0,1),(1,1),(2,1).$$

因为只购买一个网球，且重量模 $3$ 后必须不超过 $1$，所以只能购买前两种网球。两个序列价格均为 $1$，答案为 $2$。