思路与算法

令N(t)为完成t步仍未出界的起点数。任一起点的出界步数等于其贡献1的时刻数，所以答案为Σ(t≥0)N(t)。各维独立，N(t)=∏max(w_i-span_i(t),0)，span是该维前缀位移最大最小之差。 保存一周期的净位移D、最大mx和最小mn。写t=qn+r，0≤r<n。q=0直接计算前缀极差。q≥1时span=q d+c(r)，d=|D|：D>0时c=max(mx-D,mx_r)-mn；D<0时c=mx-min(mn-D,mn_r)；D=0时c=mx-mn。令A=w-c，非零d给出上界Q=min floor((A-1)/d)，零d且A≤0则Q=0。 P(z)=∏(A_i-d_i z)，其次数至多k。对每个r所求为Σ(q=1..Q)P(q)，等于系数与幂和S_j(Q)的点积。先O(k²)构造多项式及用二项式展开恒等式求幂和；S_0=Q，S_j=((Q+1)^(j+1)-1-Σ(t<j)C(j+1,t)S_t)/(j+1)。模数为素数1000000007，j+1≤11可求逆。 r每前进一步仅一维c增加0或1。增加1时通过一次线性因子除法得Pnew=Pold-Pold/(Aold-dz)，耗O(k)；Q仅可能下降1，用Q的各次幂从S中减去。若所有D为0且所有整周期极差小于宽度，存在永不出界起点，输出-1；否则尾和有限。

正确性说明

对固定维，起点合法当且仅当其坐标加所有已走前缀位移仍在[1,w]，可选坐标恰有max(w-span,0)个，故乘积和尾和公式成立。周期内各块的极值随q线性移动，按D符号取首块或末块极值即可得到上述c式。于是所有因子为正恰对应1≤q≤Q，截断后多项式求和完整而无负贡献。r增加时位移只变1，极差偏移c单调且最多增1，线性除法与幂和扣除正好维护新表达式。零漂移且全维极差小于宽度时第一周期合法起点每周期重复，确有无限者；反之零漂移有一维覆盖满宽则首周期内全部退出，非零漂移则Q有限。

复杂度

初始化保存n步、统计各维极值O(n+k)，多项式及初始幂和O(k²+k log p)，随后n个余数各O(k)。总时间O(nk+k²+k log p)，额外空间O(n+k²)。幂和的除数和非零漂移绝对值均小于p且非零，逆元存在。

易错点

答案包含t=0的起点数，出界的那一步也计数。q=0不能套整周期公式。无限只需一个起点永不出界，不要求所有起点无限。模减规范化；高次乘积先模，不直接计算宽度乘积。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll power(ll a, ll n) {
    ll r = 1;
    for (; n; n >>= 1, a = a * a % MOD)
        if (n & 1)
            r = r * a % MOD;
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> w(k);
    for (ll &v : w)
        cin >> v;
    vector<int> axis(n), step(n);
    vector<ll> D(k), mn(k), mx(k);
    for (int i = 0; i < n; i++) {
        cin >> axis[i] >> step[i];
        --axis[i];
        int z = axis[i];
        D[z] += step[i];
        mn[z] = min(mn[z], D[z]);
        mx[z] = max(mx[z], D[z]);
    }
    bool stationary = true, infinite = true;
    for (int z = 0; z < k; z++) {
        stationary &= D[z] == 0;
        infinite &= mx[z] - mn[z] < w[z];
    }
    if (stationary && infinite) {
        cout << -1 << '\n';
        return 0;
    }
    vector<ll> d(k), c(k), A(k), inv(k);
    ll Q = 1000000000;
    int degree = 0;
    for (int z = 0; z < k; z++) {
        d[z] = abs(D[z]);
        c[z] = mx[z] - mn[z] - d[z];
        A[z] = w[z] - c[z];
        if (d[z]) {
            degree++;
            Q = min(Q, (A[z] - 1) / d[z]);
            inv[z] = power(MOD - d[z], MOD - 2);
        } else if (A[z] <= 0)
            Q = 0;
    }
    if (stationary)
        Q = 0;
    Q = max(0LL, Q);
    vector<ll> P(1, 1);
    for (int z = 0; z < k; z++) {
        vector<ll> next(P.size() + (d[z] != 0));
        ll a = (A[z] % MOD + MOD) % MOD;
        for (int j = 0; j < (int)P.size(); j++) {
            next[j] = (next[j] + P[j] * a) % MOD;
            if (d[z])
                next[j + 1] = (next[j + 1] + P[j] * (MOD - d[z])) % MOD;
        }
        P.swap(next);
    }
    vector<vector<ll>> choose(degree + 2, vector<ll>(degree + 2));
    for (int i = 0; i <= degree + 1; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++)
            choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % MOD;
    }
    vector<ll> sums(degree + 1);
    sums[0] = Q % MOD;
    for (int j = 1; j <= degree; j++) {
        ll x = (power(Q + 1, j + 1) - 1 + MOD) % MOD;
        for (int t = 0; t < j; t++)
            x = (x - choose[j + 1][t] * sums[t] % MOD + MOD) % MOD;
        sums[j] = x * power(j + 1, MOD - 2) % MOD;
    }
    vector<ll> pos(k), lo(k), hi(k);
    ll answer = 0;
    for (int r = 0; r < n; r++) {
        ll count = 1;
        for (int z = 0; z < k; z++)
            count = count * max(0LL, w[z] - hi[z] + lo[z]) % MOD;
        answer = (answer + count) % MOD;
        if (Q > 0)
            for (int j = 0; j <= degree; j++)
                answer = (answer + P[j] * sums[j]) % MOD;
        int z = axis[r];
        pos[z] += step[r];
        lo[z] = min(lo[z], pos[z]);
        hi[z] = max(hi[z], pos[z]);
        ll newer = c[z];
        if (D[z] > 0)
            newer = max(mx[z] - D[z], hi[z]) - mn[z];
        else if (D[z] < 0)
            newer = mx[z] - min(mn[z] - D[z], lo[z]);
        if (newer > c[z]) {
            if (Q > 0) {
                vector<ll> B(degree);
                B[degree - 1] = P[degree] * inv[z] % MOD;
                for (int j = degree - 1; j >= 1; j--)
                    B[j - 1] = (P[j] - A[z] % MOD * B[j] % MOD + MOD) * inv[z] % MOD;
                for (int j = 0; j < degree; j++)
                    P[j] = (P[j] - B[j] + MOD) % MOD;
            }
            --A[z];
            c[z] = newer;
            ll newQ = max(0LL, (A[z] - 1) / d[z]);
            while (Q > newQ) {
                ll p = 1;
                for (int j = 0; j <= degree; j++) {
                    sums[j] = (sums[j] - p + MOD) % MOD;
                    p = p * (Q % MOD) % MOD;
                }
                --Q;
            }
        }
    }
    cout << answer << '\n';
}