#include <functional>
#include <algorithm>
#include <iostream>
#include <utility>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
//#include <bits/stdc++.h>
//#define pb push_back
//#define pf push_front
//#define ppb pop_back
//#define ppf pop_front
#define lwb lower_bound
#define upb upper_bound
#define X first
#define Y second
//#define FOR(i,j,k) for(int i = j; i < (int)(k); i++)
//#define FORV(i, v) FOR(i, 0, ((v).size()))
//#define sz(a) (int)((a).size())
//#define all(a) a.begin() , a.end()
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
//#define int long long
#define double long double
#define joon ios :: sync_with_stdio(false)
//#define cin fin
//#define cout fout

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const double pi = acos(-1);
const double eps = 1e-7;
const int MAXN=100000+100;
const int mod=1000*1000*1000 +7;
vector< pair<int,int> > N[MAXN];
long long l[MAXN],r[MAXN];
long long int f[MAXN];
long long int s[MAXN];
int n;
bool mark[MAXN];
int dp[MAXN];
int pre[MAXN];

inline void dfs(int v,int e)
{
	mark[v]=1;
	s[v]=1;
	for(int i=0;i<(int)N[v].size();i++)
	{
		int u=N[v][i].first;
		int ee=N[v][i].second;
		if( mark[ u ]==0 )
		{
			dfs( u , ee );
			s[v]+=s[ u ];
		}
	}
	f[e]= s[v]*n - s[v]*s[v] ;
	return ;
}

int main()
{
	int k;
	scanf("%d%d" , &n , &k );
	for(int i=1;i<n;i++)
	{
		int v,u,aa,bb;
		scanf("%d%d%d%d" , &v , &u , &aa , &bb );
		l[i]=aa;
		r[i]=bb;
		N[v].push_back( make_pair(u,i) );
		N[u].push_back( make_pair(v,i) );
	}
	long long flgg=(n-1)*(n-1);
	if( flgg > k )
	{
		cout<<0<<endl;
		return 0;
	}
	dfs(1,0);
	for(int i=1;i<n;i++)
		k-=(f[i]*l[i]);
	if( k < 0 )
	{
		cout<<0<<endl;
		return 0;
	}
	if( n==1 )
	{
		cout<<1<<endl;
		return 0;
	}
	for(int i=1;i<n;i++)
		dp[0]=1;
	for(int i=l[1]+1;i<=r[1];i++)
		if( (i-l[1])*f[1] <=k )
			dp[ (i-l[1])*f[1] ]=1;
	for(int i=0;i<=k;i++)
	{
		if( i-f[2] < 0 )
			pre[i]=dp[i]%mod;
		else
			pre[i]=( pre[i-f[2]]+dp[i] )%mod;
	}
	for(int i=2;i<n;i++)
	{
		memset( dp , 0 , sizeof(dp) );
		for(int j=0;j<=k;j++)
		{
			long long x1=0;
			if( j - (r[i]-l[i]+1)*f[i] >= 0 )
				x1=pre[ j-(r[i]-l[i]+1)*f[i] ]%mod;
			dp[j]=( pre[j]-x1+mod  )%mod;
		}
		if( i < n-1 )
		{
			for(int j=0;j<=k;j++)
			{
				if( j-f[i+1] < 0 )
					pre[j]=dp[j]%mod;
				else
					pre[j]=( pre[j-f[i+1]]+dp[j] )%mod;
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=k;i++)
		ans=( ans + dp[i] )%mod;
	cout<<ans<<endl;

	return 0;
}