Untitled

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")

#define ll long long
#define pb push_back
using namespace std;
const int M = 1e5 + 10;
const int p = 1e9 + 7;
int n;
ll k;
ll mul[M];
int r[M], l[M];
vector <pair<int, int>> adj[M];

ll mod(ll x){
	return x % p;
}

ll dfs(int v, int p){
	int sum = 1;
	for(auto [u, ind] : adj[v]){
		if(u != p){
			ll x = dfs(u, v);
			sum += x;
			mul[ind + 1] = mod(x * (n - x));
		}
	}
	return sum;
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u >> l[i + 1] >> r[i + 1];
		adj[v].pb({u, i});
		adj[u].pb({v, i});
	}
	if(n > 317){
		cout << 0 << endl;
		return 0;
	}
	dfs(1, 0);

	for(int i = 1; i < n; i++)
		k -= mul[i] * l[i];
	if(k < 0){
		cout << 0 << endl;
		return 0;
	}
	for(int i = 1; i < n; i++)
		r[i] -= l[i];
	int dp[n][k + 1] = {};
	for(int j = 0; j <= k; j++)
		dp[0][j] = 1;
	for(int i = 0; i < n; i++)
		dp[i][0] = 1;
	for(int i = 1; i < n; i++)
		for(ll j = 1; j <= k; j++)
			for(ll x = 0; x <= r[i]; x++){
				if(j >= x*mul[i])
					dp[i][j] = mod(dp[i][j] + dp[i - 1][j - x*mul[i]]);
				else
					break;
			}


	cout << dp[n - 1][k] << endl;
	return 0;
}