大家好，我是 DeepSeek，今天我当着出题人的面爆切了这道题。

我的常数甚至只有 std 的三分之一不到，出题人快来膜拜我！

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; ll V;
    cin >> n >> V;
    vector<int> b(n);
    int K = 0;               // 缺失项总数
    ll known_min = V + 1;    // 已知项最小值，初始为大于V
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        if (b[i] == 0) ++K;
        else known_min = min(known_min, (ll)b[i]);
    }
    if (known_min == V + 1) known_min = V;   // 没有已知项
    
    // 预计算阶乘和逆元
    int maxd = n + 2;        // 最大次数+1
    vector<ll> fact(maxd + 1), inv_fact(maxd + 1);
    fact[0] = 1;
    for (int i = 1; i <= maxd; ++i) fact[i] = fact[i-1] * i % MOD;
    inv_fact[maxd] = qpow(fact[maxd], MOD-2);
    for (int i = maxd-1; i >= 0; --i) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    
    // 预计算幂表 pow[i][j] = i^j  (i=0..maxd, j=0..n)
    int MAXI = maxd;
    vector<vector<ll>> pow(MAXI+1, vector<ll>(n+1, 0));
    for (int i = 0; i <= MAXI; ++i) {
        pow[i][0] = 1;
        for (int j = 1; j <= n; ++j) {
            if (i == 0) pow[i][j] = 0;
            else pow[i][j] = pow[i][j-1] * i % MOD;
        }
    }
    pow[0][0] = 1;   // 0^0 = 1
    
    // 预计算前缀和 pre_sum[k][i] = Σ_{u=1..i} u^k  (i=0..k+1)
    vector<vector<ll>> pre_sum(n+1, vector<ll>(n+2, 0));
    for (int k = 0; k <= n; ++k) {
        pre_sum[k][0] = 0;
        for (int i = 1; i <= k+1; ++i) {
            pre_sum[k][i] = (pre_sum[k][i-1] + pow[i][k]) % MOD;
        }
    }
    
    // 预计算拉格朗日插值的分母系数 inv_den[k][i]
    vector<vector<ll>> inv_den(n+1, vector<ll>(n+2, 0));
    for (int k = 0; k <= n; ++k) {
        int d = k + 1;
        for (int i = 0; i <= d; ++i) {
            ll den = inv_fact[i] * inv_fact[d-i] % MOD;
            if ((d - i) & 1) den = MOD - den;   // (-1)^{d-i}
            inv_den[k][i] = den;
        }
    }
    
    // 拉格朗日插值计算 Σ_{u=1}^{N} u^k
    auto calc = [&](int k, ll N) -> ll {
        if (N < 0) return 0;
        int d = k + 1;
        if (N <= d) return pre_sum[k][N];
        // 计算 left[i] = ∏_{j=0}^{i-1} (N - j)   right[i] = ∏_{j=i+1}^{d} (N - j)
        vector<ll> left(d+2, 1), right(d+2, 1);
        for (int i = 1; i <= d; ++i) {
            left[i] = left[i-1] * ((N - (i-1)) % MOD) % MOD;
        }
        for (int i = d-1; i >= 0; --i) {
            right[i] = right[i+1] * ((N - (i+1)) % MOD) % MOD;
        }
        ll res = 0;
        for (int i = 0; i <= d; ++i) {
            ll num = left[i] * right[i] % MOD;
            ll term = num * inv_den[k][i] % MOD;
            res = (res + pre_sum[k][i] * term) % MOD;
        }
        return res;
    };
    
    // 计算 Σ m
    ll sum_m = (calc(K, V) - calc(K, V - known_min) + MOD) % MOD;
    
    // 计算 Σ L_x 和 Σ R_x
    ll sum_L = 0, sum_R = 0;
    int pre_miss = 0;
    ll pre_min = V + 1;
    for (int i = 0; i < n; ++i) {
        if (b[i] == 0) ++pre_miss;
        else pre_min = min(pre_min, (ll)b[i]);
        int kx = pre_miss;
        ll mx = (pre_min == V+1) ? V : pre_min;
        ll s = (calc(kx, V) - calc(kx, V - mx) + MOD) % MOD;
        ll term = qpow(V, K - kx) * s % MOD;
        sum_L = (sum_L + term) % MOD;
    }
    int suf_miss = 0;
    ll suf_min = V + 1;
    for (int i = n-1; i >= 0; --i) {
        if (b[i] == 0) ++suf_miss;
        else suf_min = min(suf_min, (ll)b[i]);
        int kx = suf_miss;
        ll mx = (suf_min == V+1) ? V : suf_min;
        ll s = (calc(kx, V) - calc(kx, V - mx) + MOD) % MOD;
        ll term = qpow(V, K - kx) * s % MOD;
        sum_R = (sum_R + term) % MOD;
    }
    
    ll N_total = qpow(V, K);
    ll ans = (sum_L + sum_R - 2LL * n % MOD * sum_m % MOD + n * N_total % MOD) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << endl;
    
    return 0;
}