1855E - Expected Destruction - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(int i = l;i <= r;i++)
const int N = 2e3+10;
ll p = 1000000007;
ll qpow(ll a,ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res*a%p;
		a = a*a%p;
		b >>= 1;
	}
	return res;
}

ll inv2 = qpow(2,p-2);
ll dp[N][N],n,m,aa[N],ck[N][N];

ll dfs(int x,int y){
//	cerr<<'*'<<'\n';
	if(y == m+1)return m-x+1;
	if(x == y)return 0;
	if(ck[x][y])return dp[x][y];
	ck[x][y] = 1;
	dp[x][y] = (dfs(x+1,y)+1+dfs(x,y+1))*inv2%p;
	return dp[x][y];
}

void solve(){
	cin>>n>>m;
	rep(i,1,n)cin>>aa[i];
	aa[n+1] = m+1;
	ll ans = 0;
	rep(i,1,n){
		ans += dfs(aa[i],aa[i+1]);
		ans %= p;
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	solve();
    return 0;
}