We have a rectangular parallelepiped of dimensions A×B×C, divided into 1×1×1 small cubes. The small cubes have coordinates from (0, 0, 0) through (A-1, B-1, C-1).

Let p, q and r be integers. Consider the following set of abc small cubes:

\\{(\ (p + i) mod A, (q + j) mod B, (r + k) mod C\ ) | i, j and k are integers satisfying 0 ≤ i < a, 0 ≤ j < b, 0 ≤ k < c \\}

A set of small cubes that can be expressed in the above format using some integers p, q and r, is called a torus cuboid of size a×b×c.

Find the number of the sets of torus cuboids of size a×b×c that satisfy the following condition, modulo 10^9+7:

* No two torus cuboids in the set have intersection.
* The union of all torus cuboids in the set is the whole rectangular parallelepiped of dimensions A×B×C.

Constraints

* 1 ≤ a < A ≤ 100
* 1 ≤ b < B ≤ 100
* 1 ≤ c < C ≤ 100
* All input values are integers.

Input

Input is given from Standard Input in the following format:


a b c A B C


Output

Print the number of the sets of torus cuboids of size a×b×c that satisfy the condition, modulo 10^9+7.

Examples

Input

1 1 1 2 2 2


Output

1


Input

2 2 2 4 4 4


Output

744


Input

2 3 4 6 7 8


Output

0


Input

2 3 4 98 99 100


Output

471975164
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define MOD 1000000007
LL powmod(LL a, LL n){
    //if(a == 0) return 0;
    if(n == 0) return 1;
    if(n % 2) return (a*powmod(a,n-1)) % MOD;
    LL c = powmod(a, n/2);
    return (c*c) % MOD;
}
LL inv(LL a){
    return powmod(a, MOD-2);
}
LL fact[110000];
LL invfact[110000];

LL choose[210][210];

LL ncr(LL n, LL r){
    return choose[n][r];
}

LL a, b, c, A, B, C;

LL powa[110000];

void init(){
    fact[0] = 1;
    invfact[0] = 1;
    powa[0] = 1;
    LL inv2 = inv(2);
    for(LL i = 1; i < 110000; i++){
        fact[i] = (i*fact[i-1]) % MOD;
        invfact[i] = inv(fact[i]);
        powa[i] = (a * powa[i-1]) % MOD;
    }
    for(LL n = 0; n < 200; n++){
        for(LL k = 0; k < 200; k++){
            if(k > n){
                choose[n][k] = 0;
            } else if(k == 0 || k == n){
                choose[n][k] = 1;
            } else {
                choose[n][k] = choose[n-1][k-1] + choose[n-1][k];
                choose[n][k] %= MOD;
            }
        }
    }

}

int main(){

    cin >> a >> b >> c >> A >> B >> C;
    if(A % a != 0 || B % b != 0 || C % c != 0){
        cout << 0 << endl;
        return 0;
    }
    A /= a; B /= b; C /= c;
    if(A == 1) a = 1;
    if(B == 1) b = 1;
    if(C == 1) c = 1;

    init();

    LL gridhv[110][110];

    LL vnum[110];

    LL hnum[110];

    for(LL v = B; v >= 0; v--){
        for(LL w = C; w >= 0; w--){
            LL n1 = B-v;
            LL n2 = C-w;
            LL mult = (ncr(B,v) * ncr(C,w)) % MOD;
            LL pie = 0;
            for(LL j1 = 0; j1 <= n1; j1++){
                for(LL j2 = 0; j2 <= n2; j2++){
                    // restart
                    LL cmult = (ncr(n1, j1) * ncr(n2, j2)) % MOD;
                    LL add = 0;
                    if(n1-j1 == B && n2-j2 == C){
                        add = powa[B*C];
                    } else if(n1-j1 == B){
                        add = powa[B*(n2-j2) + C - (n2-j2)];
                    } else if(n2-j2 == C){
                        add = powa[C*(n1-j1) + B - (n1-j1)];
                    } else {
                        add = powa[(n2-j2)*(n1-j1) + 1];
                    }

                    add = (add * cmult) % MOD;
                    if((j1 + j2) % 2) add *= -1;
                    pie += add;
                    pie %= MOD;
                }
            }
            pie = (pie * mult) % MOD;
            if(pie < 0) pie += MOD;

            // pick grid
            if(v != B){
                pie = (pie * c) % MOD;
            }
            if(w != C){
                pie = (pie * b) % MOD;
            }
            //cout << pie << " ";
            gridhv[v][w] = pie;
        }
        //cout << endl;
    }
    //cout << endl;


    for(int z = 0; z < 2; z++){
        for(LL v = B; v >= 0; v--){
            LL n = B - v;
            LL mult = ncr(B, v);
            LL pie = (powmod(a, v) * powmod(((powmod(a, C) - a)* c) % MOD, B-v)) % MOD;        
            LL p2 = (powmod(a, v) * powmod((powmod(a, C) - a), B-v)) % MOD;
            if(v == B){
                pie = (pie - p2) % MOD;
            } else {
                pie = (pie - p2 * c) % MOD;
            }
            pie = (pie * mult) % MOD;
            if(pie < 0) pie += MOD;
            pie = (pie * b) % MOD;
            //cout << v << " " << pie << endl;
            vnum[v] = pie;
        }
        swap(b,c);
        swap(B,C);
        for(int j = 0; j < 110; j++){
            swap(vnum[j], hnum[j]);
        }
    }
    // final stage

    LL ans = 0;
    for(LL v = B; v >= 0; v--){
        for(LL w = C; w >= 0; w--){
            if(v == B && w == C){
                LL num = (b * powmod(c, B) + c * powmod(b, C) - b*c) % MOD;
                //cout << "NUM " << num << endl;
                num %= MOD;
                ans += gridhv[v][w] * powmod(num, A);
                ans %= MOD;
            } else {
                LL num = (powmod(c, v) + powmod(b,w) - 1) % MOD;
                ans += gridhv[v][w] * powmod(num, A);
                ans %= MOD;
            }
        }
    }
    for(LL v = B; v >= 0; v--){
        LL num = powmod(c, v);
        ans += vnum[v] * powmod(num, A);
        ans %= MOD;
    }
    for(LL w = C; w >= 0; w--){
        LL num = powmod(b, w);
        ans += hnum[w] * powmod(num, A);
        ans %= MOD;
    }
    ans %= MOD;
    if(ans < 0) ans += MOD;
    cout << ans << endl;
}
