Khi cắt chiếc bánh bằng ~X~ đường cắt ngang và ~Y~ đường cắt dọc, dễ thấy rằng chiếc bánh này sẽ được chia thành ~X + 1~ phần theo chiều ngang và ~Y + 1~ phần theo chiều dọc.

Mỗi miếng bánh được cắt ra đều có diện tích ~\ge S~, vì vậy nếu như ta coi phần bé nhất được cắt ra theo chiều ngang là ~i~, thì tất cả phần được cắt ra theo chiều dọc phải ~\ge j = \lceil \frac{S}{i} \rceil~. Dựa vào điều này, ta có đáp án là tổng của ~3~ trường hợp sau:

• ~i \ge \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
• ~i < \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
• ~i \ge \lceil \sqrt{S} \rceil, j < \lceil \sqrt{S} \rceil.~

Ở trường hợp ~1~, ta tính trực tiếp đáp án trong ~\mathcal{O}(1)~. Ở trường hợp ~2~, ta lặp qua tất cả các giả trị của ~i < \lceil \sqrt{S} \rceil~. Ở trường hợp ~3~, ta lặp qua tất cả các giả trị của ~j < \lceil \sqrt{S} \rceil~.

Do đó, ta đã chuyển được bài toán trở về hai bài toán con như sau:

• Chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~.
• Chia ~n~ số thành ~a~ số có giá trị bé nhất là ~b~.

Với bài toán đầu tiên, dễ thấy được đây là bài toán chia kẹo điển hình, với công thức là ~\binom{n - a \times (b - 1) - 1}{k - 1}~.

Với bài toán thứ hai, ta nhận thấy rằng đáp án là số cách chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~, trừ đi số cách chia ~n~ số thành ~a~ số đều có giá trị ~> b~. Do đó ta sẽ dùng cách tính của bài toán thứ nhất để tìm đáp án của bài toán thứ hai.

Độ phức tạp thuật toán: ~\mathcal{O}(t \times \sqrt{S})~.

Code mẫu

#include <bits/stdc++.h>
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define fid(i,a,b) for(int i=a;i>=b;i--)
#define getbit(x,i) ((x>>i)&1)
#define pii pair<int,int>
#define ll long long
#define TunaNgoo "solution"
#define maxn 1000005
using namespace std;
const int mo = 1e9 + 7;
int T, N, M, X, Y, S;
ll fact[maxn * 2], po[maxn * 2], res;
int power(int a, int b)
{
    if(b == 0) return 1;
    ll c = power(a, b / 2);
    c = (c * c) % mo;
    if(b % 2) c = (c * a) % mo;
    return c;
}
int calc(int u, int v)
{
    if(u < 0) return 0;
    v--;
    u += v;
    return fact[u] * po[v] % mo * po[u - v] % mo;
}
int tg, k;
void solve()
{
    cin >> N >> M >> X >> Y >> S;
    X++;
    Y++;
    res = 0;
    k = sqrt(S - 1) + 1;
    res = (res + 1ll * calc(N - X * k, X) * calc(M - Y * k, Y)) % mo;
    fi(i, 1, k - 1)
    {
        tg = (S - 1) / i + 1;
        if(1ll * M >= 1ll * Y * tg) res = (res + 1ll * (calc(N - X * i, X) - calc(N - X * (i + 1), X)) * calc(M - Y * tg, Y)) % mo;
        if(1ll * N >= 1ll * X * tg) res = (res + 1ll * calc(N - X * tg, X) * (calc(M - Y * i, Y) - calc(M - Y * (i + 1), Y))) % mo;
    }
    res = (res + mo) % mo;
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen(TunaNgoo".inp", "r", stdin);
    freopen(TunaNgoo".out", "w", stdout);
    #endif // ONLINE_JUDGE
    fact[0] = 1;
    fi(i, 1, 2e6) fact[i] = (fact[i - 1] * i) % mo;
    po[2000000] = power(fact[2000000], mo - 2);
    fid(i, 2e6 - 1, 0) po[i] = (po[i + 1] * (i + 1)) % mo;
    cin >> T;
    while(T--)
    {
        solve();
        cout << '\n';
    }
}