很有意思的题。
首先考虑每段数的贡献，对于 \(a_{n, j}\) 向 \(a_{k, i}\) 的贡献系数显然为 \(\dbinom{n-k}{j-i}\)。证明可以打表，你会观察到杨辉三角的结构。
然后对于一段 \((x, c), a_{n, l} = a_{n, l + 1} = \dots = a_{n, r}\)，显然总贡献为 \(\sum\limits_{j=l}^r \dbinom{n - k}{j - i}\) 这就变成了组合数前缀和问题，参见
P4345。
考虑到现在时间复杂度是 \(\mathcal{O}(mk \log_p^2 n)\) 的，有点慢，但是我们发现 \(p\) 真的很小，我们可以先拿某个 \(p^k\) 做模数，满足 \(\log_{p^k}^2 n\) 尽量小，取 \(k = 3, p^k = 2401\)，这时 Lucas 定理算组合数也变成了 \(\mathcal{O}(1)\) 的。时间复杂度 \(\mathcal{O}(mk + p^{2k})\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 5e5 + 10, p = 7, mod = 2401;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int C[mod][mod], s[mod][mod], ans[N], las[N];
int lucas(int n, int m) { return C[n / mod][m / mod] * C[n % mod][m % mod] % p; }
int f(int n, int k) {if (k < 0) return 0;if (!n || !k) return 1;if (n < mod) return s[n][min(n, k)];return (f(n / mod, k / mod - 1) * s[n % mod][mod - 1] + lucas(n / mod, k / mod) * s[n % mod][k % mod]) % p;
}
void init(int n) {for (int i = 0; i <= n; i++) {C[i][0] = 1;s[i][0] = 1;for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;for (int j = 1; j <= n; j++) s[i][j] = (s[i][j - 1] + C[i][j]) % p;}
}
void main() {int n, m, k;cin >> n >> m >> k;for (int x, c, l = 1, r = 0; m--; l = r + 1) {cin >> x >> c;r = l + c - 1;for (int i = 1; i <= k; i++) {int L = max(0, l - i), R = min(n - k, r - i);if (L <= R) {int tmp = f(n - k, R);ans[i] = (ans[i] + x * (tmp + p - las[i])) % p;las[i] = tmp;}}}for (int i = 1; i <= k; i++) cout << ans[i] << " \n"[i == k];
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);Loop1st::init(mod - 1);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}