数学、快速幂

由于模数为 $10^4$ 所以模意义下至多也只有这么多数，暴力计算。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=10'000;
int mul(int x,int y){
    int ret=1;
    x%=mod;
    for(int i=y;i;i>>=1){
        if(i&1) ret=ret*x%mod;
        x=x*x%mod;
    }
    return ret;
}
void solution(){
    int n=0,m=0,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=mod-1;i++) ans+=(n-i+mod)/mod%mod*mul(i,m)%mod;
    ans%=mod;
    printf("%d\n",ans);
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}