1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define PPC(x) __builtin_popcount((x))
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define st first
#define nd second
using namespace std;

const int maxN = 26000, mod = 1000000007;

inline void addMod(long long& a, long long b)	{   a = (a + b) % mod;  }
inline void multMod(long long& a, long long b)	{   a = a * b % mod;    }

long long qpow(long long a, long long b)
{
    long long res0 = 1;
    for (; b!=0; b>>=1)
    {
        if (b & 1)  multMod(res0, a);
        multMod(a, a);
    }
    return res0;
}

vector <pair <short, short> > G[maxN];
vector <short> pat;
vector <vector <short> > T;
//vector <short> T[10000000];
int root;

vector <int> inds[2];
int cnt[maxN];

void dfs(int v, int fat)
{
	if (root < v)
		T.pb(pat);
	for (auto p : G[v])
	{
		short u, c; tie(u, c) = p;
		if (u != fat)
		{
			pat.pb(c);
			dfs(u, v);
			pat.pop_back();
		}
	}
}

int main()
{
	int n, k;
	scanf ("%d%d", &n, &k);
	FOR(i, 1, n)
	{
		int a, b, c;
		scanf ("%d%d%d", &a, &b, &c);
		G[a].pb({b, c});
		G[b].pb({a, c});
	}
	FOR(i, 1, n+1)
		dfs(root = i, 0);
		
	inds[0].resize(T.size());
	iota(ALL(inds[0]), 0);
	FOR(i, 0, T.size())
	{
		sort(ALL(T[i]), greater <short>());
		T[i].pb(0);
	}
	
	FOR(d, 0, n-1)
	{
		vector <int> &curr = inds[d&1], &nxt = inds[(d&1) ^ 1];
		nxt.resize(0);
		
		for (int i : curr)
			cnt[T[i][d]]++;
		int ile = 0;
		short dig;
		
		FOR(c, 0, n+1)
		{
			if (ile + cnt[c] >= k)
			{
				dig = c;
				k -= ile;
				break;
			}
			ile += cnt[c];
		}
		
		for (int i : curr)
		{
			if (T[i][d] == dig)
				nxt.pb(i);
			cnt[T[i][d]] = 0;
		}
		
		if (dig == 0)	
		{
			inds[(n-1)&1] = nxt;
			break;
		}
	}
	
	int j = inds[(n-1)&1][0];
	vector <short>& t = T[j];
	t.pop_back();
	long long res = 0;
	for (short e : t)
		addMod(res, qpow(n, e));
	printf("%lld\n", res);	
	return 0;
}