“好序列”的个数

def fastPow(x, n): #快速幂
	ans = 1
	while n:
		if n & 1: ans = ans * x % MOD
		x = x * x % MOD
		n >>= 1
	return ans

def scan(): return map(int, input().split())

def dfs(now): #dfs求某个子图的节点数
	vis[now] = True
	ans = 1
	for i in G[now]:
		if vis[i] == False:
			ans += dfs(i)
	return ans

MOD = 1000000007
n, k = scan()
G = [[] for _ in range(n+1)]
for _ in range(n-1):
	u, v, color = scan()
	if color == 0: #只加红边，不加黑边
		G[u].append(v)
		G[v].append(u)
vis = [False] * (n+1)
cntBad = 0 #坏序列的个数
for i in range(1, n+1):
	if vis[i] == False:
		cntBad = (cntBad + fastPow(dfs(i), k)) % MOD
print((fastPow(n, k) - cntBad + MOD) % MOD)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100050;
vector<int>ve[maxn];
struct node{
    int nxt,to,f;
}e[maxn*2];
int cnt=0,head[maxn],vis[maxn];
void add(int u,int v,int f){
    e[cnt].to=v;
    e[cnt].f=f;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
int sz=0;
void dfs(int u,int fa){
    vis[u]=1;
    sz++;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        int f=e[i].f;
        if(v==fa||f||vis[v]) continue;
        dfs(v,u);
    }
}
const ll mod=1e9+7;
ll fpow(ll a,ll p){
    ll ans=1;
    while(p){
        if(p&1) ans=ans*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return ans;
}
int main()
{
    int n,k;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    ll ans=fpow(n,k);
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        sz=0;
        dfs(i,i);
        ans=(ans+mod-fpow(sz,k))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

import java.math.*;
import java.util.*;
public class Main{
    
    static int mod=1000000007;
    static Set<Integer>[] adj;
    static boolean[] visited;
    public static void main(String[] args){

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt(),k=scanner.nextInt();
        adj=new HashSet[n+1];
        visited=new boolean[n+1];
        BigInteger bad=new BigInteger("0");
        for(int i=1;i<=n;i++) adj[i]=new HashSet<>();
        while(scanner.hasNext()){
            int a=scanner.nextInt(),b=scanner.nextInt(),weight=scanner.nextInt();
            if(weight==0) {
                adj[a].add(b);
                adj[b].add(a);
            }
        }
        for(int i=1;i<=n;i++)
            if(!visited[i]) bad=bad.add(fastPow(dfs(i),k)).mod(new BigInteger(""+mod));
        BigInteger big=fastPow(n,k);
        System.out.println(big.subtract(bad).add(new BigInteger(mod+"")).mod(new BigInteger(mod+"")));
    }

    public static int dfs(int num){
        visited[num]=true;
        int res=1;
        for(int next:adj[num]){
            if(!visited[next]) res+=dfs(next);
        }
        return res;
    }

    public static BigInteger fastPow(int n,int k){
        if(k==0) return new BigInteger("1");
        BigInteger half=fastPow(n,k/2);
        if(k%2==0) return half.multiply(half).mod(new BigInteger(mod+""));
        else return half.multiply(half).multiply(new BigInteger(n+"")).mod(new BigInteger(mod+""));
    }
    
}