Ta quan sát thấy được quy luật của kim tự tháp ~(m, n)~ là số ~1~ sẽ được lặp lại ~n + 1~ lần, số ~m~ sẽ lặp lại ~n~ lần, và các số trong khoảng từ ~[2...m - 1]~ sẽ lặp lại ~2n~ lần:

~(n + 1) + \sum\limits_{i=2}^{m - 1} i \times 2n + m \times n~

= ~(n + 1) + (m - 2) \times (m + 1) \times n + m \times n~

= ~1 + n \times (m^2 - m - 2 + m + 1)~

= ~1 + n \times (m^2 - 1)~

Như vậy với công thức trên ta có thể trả lời mỗi truy vấn trong ~O(1)~.

Độ phức tạp: ~O(q)~

Code mẫu

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu self-destruct)
School : VNU-HCM High school for the Gifted
*/

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 1e9 + 7;
inline void add(int &x, int y, int mod = MOD) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod;}
inline void mul(int &x, int y, int mod = MOD) { x = (x * 1LL * y) % mod;}
inline int prod(int x, int y, int mod = MOD) { return mul(x, y, mod), x;}
inline int sum(int x, int y, int mod = MOD) { return add(x, y, mod), x;}
inline int bpow(int x, int y, int mod = MOD) { int ans = 1; while (y) { if (y & 1) mul(ans, x, mod); mul(x, x, mod); y >>= 1;} return ans;}
inline int Inv(int x, int mod = MOD) { return bpow(x, mod - 2, mod);}
inline int Div(int x, int y, int mod = MOD) { return prod(x, Inv(y, mod), mod);}

const int N = 1e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int dp[N], f[N], a[N];

void solve(){
    int n, m; cin >> n >> m;
    cout << sum(prod(n, (sum(prod(m, m), - 1))), 1) << endl;
}

signed main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int t = 1; cin >> t;
    while(t--){
        solve();
    }
}