Problem: Watching baseball

The other day, your competitive programming companion, Mr. O, went out to watch a baseball game. The games I watched were a total of four games, Team X and Team Y, but it was a one-sided development, and Team X won all the games. Moreover, the total score of X in the four games was 33 points, while the total score of Y was only 4 points.

Mr. O, who had lost interest in the content of the game because of the one-sided content, was pondering the question material of competitive programming while watching the game. Partly because of that, Mr. O came up with the following problems.

It is assumed that baseball teams X and Y play against each other, and the number of games X wins, the number of games Y wins, and the number of draw games are A, B, and C, respectively. It is also assumed that the total scores of X and Y in all A + B + C games are SX points and SY points, respectively. All scores are integers greater than or equal to 0. When X and Y play a total of A + B + C matches, how many different scores can be arranged for each match that meets these conditions as a result of all matches?

Here, the condition for winning in a certain game is that the score in that game is higher than the score of the opponent team, and if they are equal, it is a draw.

In addition, when calculating the sequence of scores for each match, when comparing the results of all the matches played against each other, even if the combination of scores of X and Y is the same, it is necessary to distinguish if the order is different. For example, suppose that X and Y play two games, and each wins one, there is no draw, and the total score of X and Y is one point each. In this case, the scores of X and Y in each match are expressed by the notation (X score)-(Y score), and when the results of a total of two matches are arranged, the following two conditions are satisfied.

* 1 --0, 0 --1
* 0 --1, 1 --0



These are distinguished because the order of the games is counted separately.

I want you to create a program that asks for this answer. However, since the number to be obtained can be very large, please answer the remainder obtained by dividing the number to be obtained by 1,000,000,007.

Input

The input consists of multiple datasets. Each dataset consists of one line and is expressed in the following format.

> A B C SX SY

Here, A is the number of team X wins, B is the number of team Y wins, C is the number of draw games, SX is the total score of team X, and SY is the total score of team Y. A, B, C, SX, and SY are all integers between 0 and 1,000,000, and satisfy 0 <A + B + C.

The end of the input is indicated by a line of 5 zeros.

Output

For each dataset, output one line consisting of only the remainder of the number of cases where the given conditions are met divided by 1,000,000,007.

Sample Input


1 1 0 1 1
0 0 2 3 2
4 0 0 33 4
5 4 2 20 25
4726 87361 2742 23497 162843
328324 420923 12782 834286 538297
0 0 0 0 0

Output for Sample Input


2
0
114660
512095631
673703234
166259450





Example

Input

1 1 0 1 1
0 0 2 3 2
4 0 0 33 4
5 4 2 20 25
4726 87361 2742 23497 162843
328324 420923 12782 834286 538297
0 0 0 0 0


Output

2
0
114660
512095631
673703234
166259450

Solution (in CPP):

Solution:
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long int;
const ll MOD = 1000000007;

ll mod_pow(ll x, ll n) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % MOD, n / 2);
    if(n & 1) res = (res * x) % MOD;
    return res;
}

// 髫惹ｹ mod p
vector<ll> fact;
void fact_mod(int n) {
    fact.resize(n+1);
    fact[0] = 1;
    for(int i=0; i<n; i++) {
        fact[i+1] = (fact[i] * (i+1)) % MOD;
    }
}

// 髫惹ｹ励�騾�� mod p
vector<ll> finv;
void fact_inv(int n) {
    finv.resize(n+1);
    finv[n] = mod_pow(fact[n], MOD-2);
    for(int i=n-1; i>=0; i--) {
        finv[i] = (finv[i+1] * (i+1)) % MOD;
    }
}

// fact, finv 繧剃ｽｿ縺｣縺ｦ邨�∩蜷医ｏ縺帙ｒ蜃ｺ縺
// 蝓ｺ譛ｬ逧�↓縺ｯ縺薙ｌ繧剃ｽｿ縺｣縺溘⊇縺�′縺�＞
ll combination_array(int n, int r) {
    if(n < 0 || r < 0 || n < r) return 0;
    ll x = fact[n];
    ll y = (finv[r] * finv[n-r]) % MOD;

    return (x * y) % MOD;
}

ll combination_duplicate(int x, int y) {
    return combination_array(x+y-1, y);
}

const int M = 6000010;
int main() {
    fact_mod(M);
    fact_inv(M);

    while(1) {
        ll A, B, C, X, Y; scanf("%lld%lld%lld%lld%lld", &A, &B, &C, &X, &Y);
        if(A + B + C + X + Y == 0) break;

        ll ans = 0;
        // diff 繧呈ｱｺ繧∵遠縺｡
        for(int D = 0; D <= X+Y; D++) {
            int free_pt = (X+Y-D) / 2, S = A+B+C;
            if( (X+Y-D) % 2 == 1 ) continue;
            if(free_pt > X || free_pt > Y) continue;

            // 蟾ｮ蛻�ｻ･螟悶�轤ｹ謨ｰ繧帝←蠖薙↓驟咲ｽｮ
            ll add = combination_duplicate(S, free_pt);

            // 蠑輔″蛻�￠縺ｮ菴咲ｽｮ
            (add *= combination_array(S, C)) %= MOD;

            // 蜍昴■縺ｮ菴咲ｽｮ
            (add *= combination_array(A+B, A)) %= MOD;

            // P, Q 縺ｮ險育ｮ (縺昴ｌ縺槭ｌ A 莉･荳翫�B 莉･荳翫〒縺ｪ縺代ｌ縺ｰ縺ｪ繧峨↑縺)
            int P = X - free_pt, Q = Y - free_pt;

            if(P < A || Q < B) continue;
            if(A == 0 && P > 0) continue;
            if(B == 0 && Q > 0) continue;
            P -= A, Q -= B;
            if(A > 0) (add *= combination_duplicate(A, P)) %= MOD;
            if(B > 0) (add *= combination_duplicate(B, Q)) %= MOD;

            (ans += add) %= MOD;
            // printf("D = %d, add = %lld\n", D, add);
        }
        printf("%lld\n", ans);
    }
    return 0;
}