include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double db;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef pair<int,int> PII;
#define so sizeof
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound</int></ll></int>

const db esp=1e-5;
const int N=5e2+10,M=1e3+10,Max=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 有n个城市
* @param m int整型 有m条路径
* @param s int整型 起始城市坐标
* @param t int整型 终点城市坐标
* @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
* @return int整型
*/

struct E{
    db lg;ll c;
    E(db lg=0,ll c=0):lg(lg),c(c){};
    E operator+(E b){
        return E(lg+b.lg,c*b.c%mod);
    }
};
E g[N][N];
ll C[M][M];
db lgps[M];
int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
    // write code here
    for(int i=0;i<=Max;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    lgps[0]=0;
    for(int i=1;i<=Max;i++)
        lgps[i]=lgps[i-1]+log(i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=(i==j)?E(0,1):E(inf*1.0,0);
    for(auto i:edge){
        int a=i[0], b=i[1], c=i[2], d=i[3];
        db lg=lgps[c]-lgps[c-d]-lgps[d];
        if(g[a][b].lg>lg)
            g[a][b]=E(lg,C[c][d]), g[b][a]=E(lg,C[c][d]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(g[i][j].lg>g[i][k].lg+g[k][j].lg)
                    g[i][j]=g[i][k]+g[k][j];
    }

    return g[s][t].c;
}

}T;