1842G - Tenzing and Random Operations - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000010

const int N = 5010;

int fastpower(int num,int po){
	int fres = 1;
	while(po > 0){
		if(po & 1)
			fres = (long long)fres * num % mod;
		po >>= 1;
		num = (long long)num * num % mod;
	}
	return fres;
}

inline void add(int &x,int y){x += y;if(x >= mod) x -= mod;}

inline void sub(int &x,int y){x -= y;if(x < 0) x += mod;}

int n , m , v;

int arr[N];

int dp[N][N];

int main(){
	scanf("%d%d%d",&n,&m,&v);
	for(int i = 0 ;i < n;i++){
		scanf("%d",&arr[i]);
	}

	int cur = fastpower(fastpower(n , m) , mod - 2);
	for(int i = 0 ;i <= n;i++) dp[n][i] = fastpower(n , m - i);

	for(int i = n - 1;i >= 0;i--){
		for(int j = 0 ; j <= min(i , m);j++){
			dp[i][j] = (long long)arr[i] * dp[i + 1][j] % mod;
			add(dp[i][j], (long long)((long long)j * v % mod) * dp[i + 1][j] % mod);
			if(j < m) 
				add(dp[i][j] , (long long)((long long)((long long)(m - j) * (i + 1) % mod) * v % mod) * dp[i + 1][j + 1] % mod);
		}
	}
	cout << (long long)dp[0][0] * cur % mod << endl;

	return 0;
}