You are given a tree (a connected undirected graph without cycles) of n vertices. Each of the n - 1 edges of the tree is colored in either black or red.

You are also given an integer k. Consider sequences of k vertices. Let's call a sequence [a_1, a_2, …, a_k] good if it satisfies the following criterion:

  * We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from a_1 and ending at a_k. 
  * Start at a_1, then go to a_2 using the shortest path between a_1 and a_2, then go to a_3 in a similar way, and so on, until you travel the shortest path between a_{k-1} and a_k.
  * If you walked over at least one black edge during this process, then the sequence is good. 

<image>

Consider the tree on the picture. If k=3 then the following sequences are good: [1, 4, 7], [5, 5, 3] and [2, 3, 7]. The following sequences are not good: [1, 4, 6], [5, 5, 5], [3, 7, 3].

There are n^k sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 10^9+7.

Input

The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 100), the size of the tree and the length of the vertex sequence.

Each of the next n - 1 lines contains three integers u_i, v_i and x_i (1 ≤ u_i, v_i ≤ n, x_i ∈ \{0, 1\}), where u_i and v_i denote the endpoints of the corresponding edge and x_i is the color of this edge (0 denotes red edge and 1 denotes black edge).

Output

Print the number of good sequences modulo 10^9 + 7.

Examples

Input


4 4
1 2 1
2 3 1
3 4 1


Output


252

Input


4 6
1 2 0
1 3 0
1 4 0


Output


0

Input


3 5
1 2 1
2 3 0


Output


210

Note

In the first example, all sequences (4^4) of length 4 except the following are good: 

  * [1, 1, 1, 1]
  * [2, 2, 2, 2]
  * [3, 3, 3, 3]
  * [4, 4, 4, 4] 



In the second example, all edges are red, hence there aren't any good sequences.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> 
#define MOD  (int)(1e9+7)
#define SIZE (int)(1e5+5)
#define all(x) x.begin(),x.end()
#define lb     lower_bound
#define ub     upper_bound
#define pb     push_back
#define F      first
#define S      second
#define cnt_set1(x) __builtin_popcountll(x)  
#define trailing_0(x) __builtin_ctz(x)
#define PI (double) acos(-1) 
#define prDouble(x) cout<<fixed<<setprecision(10)<<x;
#define IOfast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define get_element_by_key(x) find_by_order(x) 
#define get_key(x)   order_of_key(x)
#define debug(x) cout<<#x<<" = "<<x<<"\n";
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
using namespace std;
using namespace __gnu_pbds; 
//less_int<int>

typedef tree<int64_t, null_type,less<int64_t>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

typedef tree<int64_t, null_type, less_equal<int64_t>, rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;
//find_by_order(x) -> returns an iterator to the element at a given position
//order_of_key(x) -> returns the position of a given element

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args){
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}

///pair cout
template<typename T,typename G> print(pair<T,G> p){ cout<<"{"<<p.F<<","<<p.S<<"},";  }
///vector cout 
template<typename T> print(vector <T> v){ for(auto item:v)cout<<item<<" ";cout<<"\n";} 
///set cout
template<typename T> print(set <T> v){ for(auto item:v)cout<<item<<" ";cout<<"\n";} 
///multiset cout
template<typename T> print(multiset <T> v){ for(auto item:v)cout<<item<<" ";cout<<"\n";} 
//map cout
template<typename T,typename G> print(map <T,G> v){ for(auto item:v) cout<<"{"<<item.first<<"=>"<<item.second<<"},"<<" ";cout<<"\n";} 

int64_t power(int64_t base,int exp,int64_t mod)
{
    if (exp == 0) return 1;
    if (exp == 1) return base % mod;
    
    int64_t t = power(base, exp / 2,mod) % mod;
    t = (t * t) % mod;
    if (exp % 2 == 0)
     return t;
    else
     return (base * t) % mod;
}

//void seiveErath(int n)
vector<int64_t> seiveErath(int n)
{
  vector<int64_t> prime;
  int mark[n+1]={0};
  for(int i=2;i<=n;i++)
  {
    if(!mark[i])
    { 
      prime.pb(i);
      int temp=2*i;
      while(temp<=n){ mark[temp] = 1;temp+=i;} 
    }  
  }
  return prime;    
}

//int64_t dp[(int)4e8];
int visited[(int)2e5 + 1];
vector <pair<int,int>> graph[(int)2e5 + 1];

int component(int node)
{
  if(visited[node])
    return 0;
  visited[node]=1;
  int ans=1;
  for(auto &item:graph[node])
    if(item.S == 0)
      ans+=component(item.F);
   return ans; 
}

int main()
{
  IOfast;
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
  #endif   
  
  int q=1;
  //seiveErath((int)2e7);
  //cin>>q;
  //memset(dp,-1,sizeof(dp));
  
  while(q--)
  {
    int n,k,u,v,c;
    cin>>n>>k;
    
    for(int i=2;i<=n;i++)
    {
      cin>>u>>v>>c;
      graph[u].pb({v,c});
      graph[v].pb({u,c});
    }
    
    int sum=0;
    for(int i=1;i<=n;i++)
    { 
      if(visited[i] == 1) continue;

      int cmpnt = component(i);
      sum+=power(cmpnt,k,MOD);
    }
    
    cout<<(power(n,k,MOD)-sum)%MOD;
  }  
  
  //REMEMBER TO REMOVE ALL error() 
  //BECAUSE IT PASSES CODEFORCES JUDGE BUT 
  //IT SLOWS DOWN CODE TREMENDOUSLY AND CAN CAUSE TLE
  //REMEMBER ONCE 77MS CODE BECAME 865MS CODE ON ADDING error()  
  
  #ifndef ONLINE_JUDGE
  cout << "\nTimes Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
  #endif  
  
  return 0;
}