#define READ_NUM_TEST_CASES  false
#define USE_FAST_IO          false

////////////////////////////////////////////////////////////////////////////////
// AMALGAMATE: "include/template.hpp" BEGINS HERE
//
	
	
	#include <bits/stdc++.h>
	using namespace std;
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "include/abbrevs.hpp" BEGINS HERE
	//
		
		#define UI unsigned int
		
		#define LL long long
		#define ULL unsigned long long
		
		#define PII pair<int,int>
		
		
		#define RI ri()
		#define RUI rui()
		
		#define RLL rll()
		#define RULL rull()
		
		#define RSTR rstr()
		
		
		
		#define FO(i,a,b) for(int i=(a); i<int(b); ++i)
		#define OF(i,a,b) for(int i=(b)-1; i>=int(a); --i)
		
		#define FOR(i,n) FO(i,0,n)
		#define ROF(i,n) OF(i,0,n)
		
		
		#define MIN(a,b) ((a)<(b) ? (a) : (b))
		#define MAX(a,b) ((b)<(a) ? (a) : (b))
		
		#define REMIN(a,b) ((a) = min(a,b))
		#define REMAX(a,b) ((a) = max(a,b))
		
		#define ALL(c) (c).begin(),(c).end()
		
		#define SQR(x) ((x)*(x))
		
		
		
		bool is_pow(int x) {
			return (x&(x-1)) == 0;
		}
		
	
	//
	// AMALGAMATE: "include/abbrevs.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	#if USE_FAST_IO
		
		////////////////////////////////////////////////////////////////////////////////
		// AMALGAMATE: "include/fast-io.hpp" BEGINS HERE
		//
			
			
			//#define FREAD  fread
			//#define FWRITE fwrite
			
			#define FREAD  fread_unlocked
			#define FWRITE fwrite_unlocked
			
			
			
			
			
			
			struct Buffer {
				FILE* const stream;
				const int buffer_size;
			
				uint8_t* const buff;
				int pos = 0;
			
				Buffer(FILE* a_stream, int a_buffer_size) :
						stream( a_stream ),
						buffer_size( a_buffer_size ),
						buff( new uint8_t[ buffer_size ] ) {
					setvbuf(stream, NULL, _IONBF, 0);
				}
			
				~Buffer() {
					delete[] buff;
				}
			};
			
			
			
			
			
			
			
			
			
			
			class In_Buffer : private Buffer {
			public:
				In_Buffer(FILE* a_stream, int a_buffer_size) : Buffer(a_stream, a_buffer_size) {
					FREAD(buff, 1, buffer_size, stream);
				}
			
			public:
				void prepare(int num_chars) {
					auto remaining = buffer_size - pos;
					if(remaining >= num_chars) return;
			
					assert(remaining >= 0); // prevent compiler warning
					memcpy(buff, buff+pos, remaining);
			
					int read = FREAD(buff+remaining, 1, pos, stream);
					int block_end = remaining + read;
					memset(buff + block_end, 0, buffer_size - block_end);
					pos = 0;
				}
			
			public:
				char get_unchecked() {
					return buff[ pos++ ];
				}
			};
			
			
			template<class INT>
			INT read_unsigned(In_Buffer& buff) {
				buff.prepare(25);
			
				char c = buff.get_unchecked();
				while(c < '-') c = buff.get_unchecked();
			
				INT r = 0;
			
				for(;;) {
					if(c < '0') return r;
					c -= '0';
					r = r*10 + c;
					c = buff.get_unchecked();
				}
			}
			
			
			template<class INT>
			INT read_signed(In_Buffer& buff) {
				buff.prepare(25);
			
				char c = buff.get_unchecked();
				while(c < '-') c = buff.get_unchecked();
			
				bool minus = false;
				if(c=='-') {
					c = buff.get_unchecked();
					minus = true;
				}
			
				INT r = 0;
			
				for(;;)
				{
					if(c < '0') return minus ? -r : r;
					r = r*10 + (c-'0');
					c = buff.get_unchecked();
				}
			}
			
			
			
			
			In_Buffer& operator>>( In_Buffer& buff, char& c) {
				buff.prepare(1);
				c = buff.get_unchecked();
				return buff;
			}
			
			
			
			In_Buffer& operator>>( In_Buffer& buff, UI& r) { r = read_unsigned<UI>(buff); return buff; }
			In_Buffer& operator>>( In_Buffer& buff, ULL& r) { r = read_unsigned<ULL>(buff); return buff; }
			
			In_Buffer& operator>>( In_Buffer& buff, int& r) { r = read_signed<int>(buff); return buff; }
			In_Buffer& operator>>( In_Buffer& buff, LL& r) { r = read_signed<LL>(buff); return buff; }
			
			In_Buffer& operator>>( In_Buffer& buff, string& r) {
				r.clear();
			
				char c = buff.get_unchecked();
				while(c <= ' ') c = buff.get_unchecked();
			
				do {
					r.push_back( c );
					c = buff.get_unchecked();
				} while(c > ' ');
			
				return buff;
			}
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			class Out_Buffer : private Buffer {
			public:
				Out_Buffer(FILE* a_stream, int a_buffer_size) : Buffer(a_stream, a_buffer_size) {}
			
				~Out_Buffer() {
					flush();
				}
			
			public:
				void prepare(int num_chars) {
					if(buffer_size - pos >= num_chars) return;
					flush();
				}
			
				void flush() {
					FWRITE(buff, 1, pos, stream);
					pos = 0;
				}
			
			public:
				void put_unchecked(const char& c) {
					buff[ pos++ ] = c;
				}
			
				void put_unchecked(const char* str, int len) {
					memcpy(buff+pos, str, len);
					pos += len;
				}
			};
			
			
			
			
			
			
			template<class INT>
			void write_signed(Out_Buffer& buff, const INT& i) {
				buff.prepare(25);
			
				if(i == 0) {
					buff.put_unchecked('0');
					return;
				}
			
				auto ci = i;
			
				if(ci < 0) {
					buff.put_unchecked('-');
					ci = -ci;
				}
			
				const int sz = 25;
				char temp[sz];
				int pos = sz;
			
				while(ci) {
					temp[ --pos ] = '0' + ci%10;
					ci/=10;
				}
			
				buff.put_unchecked(temp+pos, sz-pos);
			}
			
			
			
			template<class INT>
			void write_unsigned(Out_Buffer& buff, const INT& i) {
				buff.prepare(25);
			
				if(i==0) {
					buff.put_unchecked('0');
					return;
				}
			
				const int sz = 25;
				char temp[sz];
				int pos = sz;
			
				auto ci = i;
			
				while(ci) {
					temp[ --pos ] = '0' + ci%10;
					ci/=10;
				}
			
				buff.put_unchecked(temp+pos, sz-pos);
			}
			
			
			
			Out_Buffer& operator<<( Out_Buffer& buff, const char& c) {
				buff.prepare(1);
				buff.put_unchecked( c );
				return buff;
			}
			
			Out_Buffer& operator<<( Out_Buffer& buff, const UI& r) { write_unsigned<UI>(buff, r); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const ULL& r) { write_unsigned<ULL>(buff, r); return buff; }
			
			Out_Buffer& operator<<( Out_Buffer& buff, const int& r) { write_signed<int>(buff, r); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const LL& r) { write_signed<LL>(buff, r); return buff; }
			
			Out_Buffer& operator<<( Out_Buffer& buff, const char* cstr) { auto len = strlen(cstr); buff.prepare(len); buff.put_unchecked(cstr, len); return buff; }
			Out_Buffer& operator<<( Out_Buffer& buff, const string& str) { buff.prepare( str.size() ); buff.put_unchecked(str.data(), str.size()); return buff; }
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			#define BUFF_SIZE 32768
			In_Buffer  fast_cin(  stdin,  BUFF_SIZE );
			Out_Buffer fast_cout( stdout, BUFF_SIZE );
			//Out_Buffer fast_cerr( stderr, BUFF_SIZE );
			
			char fast_endl = '\n';
			
		
		//
		// AMALGAMATE: "include/fast-io.hpp" ENDS HERE
		////////////////////////////////////////////////////////////////////////////////
		
		#define cin fast_cin
		#define cout fast_cout
		#define endl fast_endl
	#else
		
		////////////////////////////////////////////////////////////////////////////////
		// AMALGAMATE: "include/slow-io.hpp" BEGINS HERE
		//
			
			struct Slow_IO_Singleton {
				Slow_IO_Singleton() {
					ios_base::sync_with_stdio( false );
			
					std::cin.tie( nullptr );
					std::cout.tie( nullptr );
			
					setlocale(LC_ALL,"C");
			
					const int buffer_size = 32768;
			
					static char stdin_buffer[ buffer_size ];
					static char stdout_buffer[ buffer_size ];
			
					cin.rdbuf()->pubsetbuf( stdin_buffer, buffer_size );
					cout.rdbuf()->pubsetbuf( stdout_buffer, buffer_size );
				}
			
				~Slow_IO_Singleton() {
			
				}
			};
			
			
			Slow_IO_Singleton slow_io_singleton;
			
		
		//
		// AMALGAMATE: "include/slow-io.hpp" ENDS HERE
		////////////////////////////////////////////////////////////////////////////////
		
		#if USE_FAST_ENDL
			#define endl '\n'
		#endif
	#endif
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "include/abbrevs-io.hpp" BEGINS HERE
	//
		
		
		
		
		int ri()   { int r; cin >> r; return r; }
		UI  rui()  { UI r; cin >> r; return r; }
		
		LL  rll()  { LL r;  cin >> r; return r; }
		ULL rull() { ULL r; cin >> r; return r; }
		
		string rstr() {string s; cin >> s; return s; }
		
	
	//
	// AMALGAMATE: "include/abbrevs-io.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	
	////////////////////////////////////////////////////////////////////////////////
	// AMALGAMATE: "include/debug.hpp" BEGINS HERE
	//
		
		
		#define ASS(x) assert(x)
	
	//
	// AMALGAMATE: "include/debug.hpp" ENDS HERE
	////////////////////////////////////////////////////////////////////////////////
	
	
	
	
	//
	// for salgo
	#define CONTEST_MODE
	
	namespace salgo {};
	using namespace salgo;
	//

//
// AMALGAMATE: "include/template.hpp" ENDS HERE
////////////////////////////////////////////////////////////////////////////////






//
// snippets/int-pow.hpp
//
template<class T, class E, class OP>
T int_pow(T a, E exp, const OP& op, const T& neutral) {

	auto r = neutral;
	while(exp != 0) {
		if((exp & 1) != 0) {
			op(r, a);
			--exp;
		}
		else{
			exp >>= 1;
			op(a, a);
		}
	}
	return r;
}

template<class T, class E>
T int_pow(const T& a, const E& exp) {
	auto lambda = [](T& aa, const T& bb){ aa *= bb; };
	return int_pow<T,E,decltype(lambda)>(a, exp, lambda, T(1));
}






//
// snippets/modulo.hpp
//
uint32_t MOD = 1e9 + 7;

class Modulo {
public:
	using H = uint32_t;
	H h = 0;

public:
	Modulo() = default;
	Modulo(H x) : h( x % MOD ) {}

	Modulo(const Modulo&) = default;

public:
	Modulo& operator+=(const Modulo& o) {
		h += o.h;
		if(h >= MOD) h -= MOD;
		return *this;
	}

	Modulo& operator-=(const Modulo& o) {
		h = MOD + h - o.h;
		if(h >= MOD) h -= MOD;
		return *this;
	}

	Modulo& operator*=(const Modulo& o) {
		h = (1ULL * h * o.h) % MOD;
		return *this;
	}

	Modulo& operator/=(const Modulo& o) {
		const auto TOTIENT = MOD-1;
		*this *= int_pow(o, TOTIENT-1);
		return *this;
	}

	bool operator==(const Modulo& o) const { return h == o.h; }
	bool operator!=(const Modulo& o) const { return h != o.h; }


	Modulo operator+(const Modulo& o) const { return Modulo(*this) += o; }
	Modulo operator-(const Modulo& o) const { return Modulo(*this) -= o; }
	Modulo operator*(const Modulo& o) const { return Modulo(*this) *= o; }
	Modulo operator/(const Modulo& o) const { return Modulo(*this) /= o; }



	Modulo& operator--()    { if(h == 0) h = MOD; --h; return *this; }
	Modulo& operator++()    { ++h; if(h == MOD) h = 0; return *this; }
	Modulo  operator--(int) { auto m = *this; --(*this); return m; }
	Modulo  operator++(int) { auto m = *this; ++(*this); return m; }



	explicit operator H() const { return h; }
};

ostream& operator<<(ostream& os, const Modulo& modulo) {
	return os << modulo.h;
}






#define DBG if(0) cerr



struct Vert {
	struct VE {
		int16_t to;
		int16_t p;
	};
	vector<VE> tos;
};

const int MAX_N = 25'009;
Vert verts[MAX_N];

using Chv = vector<int16_t>;


ostream& operator<<(ostream& os, const Chv& chv) {
	cout << "[";
	FOR(i, (int)chv.size()) {
		cout << chv[i];
		if(i != (int)chv.size()-1) cout << ", ";
	}
	return os << "]";
}


struct Tour_Node {
	int16_t v;
	int16_t p;
	int8_t level_delta;
	bool first_vis = false;
};

vector<Tour_Node> tour;

int where_in_tour[MAX_N];
int last_in_tour = 0;

void tour_dfs(int16_t v, int parent) {
	DBG << "tour_dfs: " << v << " at " << tour.size() << endl;

	where_in_tour[v] = tour.size();
	last_in_tour = tour.size();

	for(auto& ve : verts[v].tos) {
		if(ve.to == parent) continue;

		tour.push_back({ve.to, ve.p, int8_t(1)});
		tour.back().first_vis = true;
		tour_dfs(ve.to, v);
		tour.push_back({v, ve.p, int8_t(-1)});
	}
}


// vector<Chv> samples;


struct Test_Case {


	void solve() {
		// cout << "Case #" << icase+1 << ": ";
		const int N = RI;
		int K = RI;

		vector<int> p_remap(N);
		vector<int> p_remap_inv(N);

		int NUM_P = 0;

		{
			set<int> all_p;

			FOR(i, N-1) {
				int16_t a = RI-1;
				int16_t b = RI-1;
				int16_t p = RI-1;

				verts[a].tos.push_back({b,p});
				verts[b].tos.push_back({a,p});

				all_p.insert(p);
			}

			for(auto& p : all_p) {
				p_remap[p] = NUM_P;
				p_remap_inv[NUM_P] = p;
				++NUM_P;
			}

			for(auto& v : verts) {
				for(auto& to : v.tos) {
					to.p = p_remap[to.p];
				}
			}
		}

		vector<int> p_domains(NUM_P);
		for(auto& v : verts) {
			for(auto& ve : v.tos) {
				p_domains[ve.p]++;
			}
		}
		for(auto& e : p_domains) e /= 2;
		for(auto& e : p_domains) e += 1;


		cerr << "P domains:" << endl;
		for(auto& e : p_domains) cerr << e << " ";
		cerr << endl;


		cerr << "NUM_P compressed to " << NUM_P << " from " << N << endl;

		cerr << "building tour" << endl;
		tour_dfs(0, -1);
		//tour.back().first_vis = true;
		cerr << "building tour done (" << tour.size() << ")" << endl;
		cerr << "last in tour: " << last_in_tour << endl;

		// cerr << endl << "FULL TOUR:" << endl;
		// FOR(i,tour.size()) cerr << i << ": " << tour[i].level_delta << " " << tour[i].p << " " << tour[i].

		// samples.reserve(SAMPLES);


		cerr << "collect samples" << endl;


		// vector<Chv> all;
		// LL count = 0;

		int array_size = 1;
		LL MAX_COLLECT = 1'000'000'000 / 4   *   2/3;

		int num_p_collect = 0;

		while(NUM_P-1 - num_p_collect >= 0 && 1LL * array_size * p_domains[ NUM_P-1 - num_p_collect ] <= MAX_COLLECT) {
			array_size *= p_domains[ NUM_P-1 - num_p_collect ];
			++num_p_collect;
		}

		cerr << "collecting " << num_p_collect << " last dimensions, total " << array_size << " elements" << endl;


		int want_end_hash = 0;

		int expect_last_num = 0;

		{
			deque<int32_t> collection(array_size);

			// LL num_vis = 0;
			FOR(v0, N) {
				Chv chv(NUM_P);

				DBG << endl << "collect paths for v0 " << v0 << endl;
				int i0 = where_in_tour[v0];
				int level = 0;
				for(int i = i0; i<=last_in_tour; ++i) {
					auto& t = tour[i];
					// cerr << i << ": tour edge   level_delta == " << (int)t.level_delta << "   p == " << t.p << "   v == " << t.v << endl;
					if(level + t.level_delta < 0) {
						chv[t.p] += 1;
					}
					else {
						chv[t.p] += t.level_delta;
						level += t.level_delta;
					}

					if(t.first_vis) {
						// static int counter = 1234567;
						// if((counter & 0xffff) == 0) {
						// 	samples.push_back(chv);
						// }
						// ++counter;
						// ++num_vis;

						DBG << "chv at tour idx " << i << "   " << chv << endl;

						// cerr << "first_diff " << first_diff << endl;

						int idx = 0;

						FOR(jj, num_p_collect) {
							idx *= p_domains[NUM_P-1 - jj];
							idx += chv[NUM_P-1 - jj];
						}

						DBG << "->hash value " << idx << endl;

						collection[idx] += 1;

						// all.push_back(chv);
					}
				}
			}


			cerr << "initial K == " << K << endl;

			LL c_sum = 0;

			// FOR(i, array_size) {
			// 	cerr << "hash " << i << " -> " << collection[i] << endl;
			// }

			FOR(i, array_size) {
				c_sum += collection[i];

				// cerr << "want K == " << K << endl;
				// cerr << c_sum << " += " << collection[i] << endl;

				if(c_sum >= K) {
					c_sum -= collection[i]; // undo
					want_end_hash = i;

					expect_last_num = collection[i];

					break;
				}
			}

			cerr << "selected hash: " << want_end_hash << endl;
			cerr << "c_sum == " << c_sum << endl;

			assert(c_sum < K);

			K -= c_sum;
			cerr << "remaining K: " << K << endl;
			assert(K >= 0);
		}


		vector<Chv> all;

		// LL num_vis = 0;
		FOR(v0, N) {
			Chv chv(NUM_P);

			DBG << endl << "collect paths for v0 " << v0 << endl;
			int i0 = where_in_tour[v0];
			int level = 0;
			for(int i = i0; i<=last_in_tour; ++i) {
				auto& t = tour[i];
				// cerr << i << ": tour edge   level_delta == " << (int)t.level_delta << "   p == " << t.p << "   v == " << t.v << endl;
				if(level + t.level_delta < 0) {
					chv[t.p] += 1;
				}
				else {
					chv[t.p] += t.level_delta;
					level += t.level_delta;
				}

				if(t.first_vis) {
					// static int counter = 1234567;
					// if((counter & 0xffff) == 0) {
					// 	samples.push_back(chv);
					// }
					// ++counter;
					// ++num_vis;

					// DBG << "chv at tour idx " << i << "   " << chv << endl;

					// cerr << "first_diff " << first_diff << endl;

					int idx = 0;

					FOR(jj, num_p_collect) {
						idx *= p_domains[NUM_P-1 - jj];
						idx += chv[NUM_P-1 - jj];
					}

					if(idx == want_end_hash) {
						Chv trunc( chv.begin(), chv.end() - num_p_collect );
						all.push_back(trunc);
					}

					// all.push_back(chv);
				}
			}
		}

		cerr << "collected " << all.size() << " elements for sorting" << endl;

		cerr << "expect_last_num " << expect_last_num << endl;

		assert((int)all.size() == expect_last_num);



		vector<int> s_remap( all.size() );
		FOR(i, all.size()) s_remap[i] = i;




		// cerr << "radix sort samples" << endl;
		// FOR(i,N) {
		// 	stable_sort(ALL(s_remap), [&](auto& _a, auto& _b) {
		// 		auto& a = all[_a];
		// 		auto& b = all[_b];
		// 		return a[i] < b[i];
		// 	});
		// }
		// cerr << "radix sort samples done" << endl;


		cerr << "sorting" << endl;
		sort(ALL(s_remap), [&](auto& _a, auto& _b) {
			auto& a = all[_a];
			auto& b = all[_b];
			OF(i, 0, a.size()) if(a[i] != b[i]) return a[i] < b[i];
			return false;
		});

		cerr << "sorting done" << endl;


		auto& resx = all[ s_remap[K-1] ];
		cerr << "resx dim " << resx.size() << endl;

		Modulo res = 0;

		FOR(i, resx.size()) {
			res += int_pow(Modulo(N), p_remap_inv[i]+1) * Modulo(resx[i]);
		}

		// decode hash
		vector<int> remaining;
		FOR(i, num_p_collect) {
			int val = want_end_hash % p_domains[NUM_P - num_p_collect + i];
			want_end_hash /= p_domains[NUM_P - num_p_collect + i];

			remaining.push_back(val);
		}

		cerr << "decoded remaining: ";
		for(auto& e : remaining) cerr << e << " ";
		cerr << endl;

		assert((int)resx.size() + (int)remaining.size() == NUM_P);

		FOR(i, remaining.size()) {
			res += int_pow(Modulo(N), p_remap_inv[resx.size() + i]+1) * Modulo(remaining[i]);
		}

		cout << res << endl;

	}

	int icase = -1;
}; // struct Test_Case



int main() {
	int num_cases = READ_NUM_TEST_CASES ? RI : 1;
	
	FOR(i, num_cases) {
		Test_Case tc;
		tc.icase = i;
		tc.solve();
	}

	return 0;
}