随机后缀操作

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定长度为 $n$ 的数组 $a$ 和整数 $v$。进行 $m$ 次相互独立的随机操作：每次等概率选择 $i\in[1,n]$，并把所有 $j\ge i$ 的 $a_j$ 增加 $v$。

求所有操作结束后 $\prod_{i=1}^n a_i$ 的期望值，对 $10^9+7$ 取模。若期望为最简分数 $p/q$，输出 $p\cdot q^{-1}\bmod(10^9+7)$。

输入格式

第一行三个整数 $n,m,v$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出期望值的模意义结果。

样例输入 1

2 2 5
2 2

样例输出 1

84

样例输入 2

5 7 9
9 9 8 2 4

样例输出 2

975544726

数据范围

$1\le n\le5000$，$1\le m,v,a_i\le10^9$。

每个测试点独立计分。