Expert.
Put your skills to the test.

Problem summary

Starting at (0,0), reach (N,M) in exactly K steps. Each step independently increases x by an integer from 0 through A and y by an integer from 0 through B. Count sequences modulo 1000000007.

Constraints

1 ≤ N,M,A,B,K ≤ 10000.

Worked example

Official example, transcribed with whitespace restored from the PDF.

3 1 2 3 2

4

Solution analysis

1. The coordinate choices are independent, so multiply two one-dimensional counts. In one coordinate we need K nonnegative increments summing to X, each at most L.
2. Without upper bounds, stars and bars gives C(X+K−1,K−1). Apply inclusion-exclusion to increments exceeding L: choose j offending positions, subtract L+1 from each, and count the remaining nonnegative sum. The result is Σ(−1)^j C(K,j)C(X−j(L+1)+K−1,K−1).
3. Precompute factorials and inverse factorials through max(N,M)+K, which is below the modulus. In the sample, x=3 in two increments bounded by 2 has choices (1,2),(2,1); y=1 has choices (0,1),(1,0), giving 2×2=4.

Why it works

For a fixed chosen set of j increments violating the bound, subtracting L+1 from each gives a bijection to unrestricted nonnegative solutions of the reduced sum. Inclusion-exclusion counts precisely solutions with no violations. Independent x and y sequences combine bijectively into two-dimensional jump sequences, so their counts multiply.

Watch out. Include zero increments and exactly K steps; stop inclusion-exclusion when the reduced sum becomes negative.

An independently written complete program with standard headers.

// Key idea: For a fixed chosen set of j increments violating the bound, subtracting L+1 from each
// gives a bijection to unrestricted nonnegative solutions of the reduced sum. Inclusion-exclusion
// counts precisely solutions with no violations.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const long long MOD=1000000007;
long long power(long long a,long long e){
    long long result=1;
    while(e!=0){
        if(e&1){
            result=result*a%MOD;
        }
        a=a*a%MOD;
        e>>=1;
    }
    return result;
}
int main(){
    int n,m,a,b,k;
    cin>>n>>m>>a>>b>>k;
    int limit=max(n,m)+k;
    vector<long long>fact(limit+1,1),inverse(limit+1,1);
    for(int i=1;i<=limit;++i){
        fact[i]=fact[i-1]*i%MOD;
    }
    inverse[limit]=power(fact[limit],MOD-2);
    for(int i=limit;i>0;--i){
        inverse[i-1]=inverse[i]*i%MOD;
    }
    auto choose=[&](int x,int y)->long long{
        if(y<0||y>x){
            return 0;
        }
        return fact[x]*inverse[y]%MOD*inverse[x-y]%MOD;
    };
    auto count=[&](int x,int bound){
        long long result=0;
        for(int j=0;j<=k&&j*(bound+1)<=x;++j){
            int remaining=x-j*(bound+1);
            long long term=choose(k,j)*choose(remaining+k-1,k-1)%MOD;
            result=(result+(j%2?MOD-term:term))%MOD;
        }
        return result;
    };
    cout<<count(n,a)*count(m,b)%MOD<<'\n';
}