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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.AbstractSet;
import java.util.Set;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Random;
import java.util.AbstractMap;
import java.util.Map;
import java.io.Writer;
import java.util.Map.Entry;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author @Ziklon
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    CEdgyTrees solver = new CEdgyTrees();
    solver.solve(1, in, out);
    out.close();
  }

  static class CEdgyTrees {
    long MOD = (int) 1e9 + 7;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.readInt(), k = in.readInt();
      RecursiveIndependentSetSystem ris = new RecursiveIndependentSetSystem(n);

      for (int i = 0; i + 1 < n; ++i) {
        int x = in.readInt() - 1, y = in.readInt() - 1, z = in.readInt();
        if (z == 0) ris.join(x, y);
      }

      Counter<Integer> counter = new Counter<>();
      for (int i = 0; i < n; ++i) counter.add(ris.get(i));

      if (ris.getSetCount() == 1) {
        out.printLine(0);
        return;
      }

      long ans = IntegerUtils.power(n, k, MOD);

      for (long setCount : counter.values()) {

        ans = (ans - IntegerUtils.power(setCount, k, MOD) + MOD) % MOD;
      }

      out.printLine(ans);
    }
  }

  static class EHashMap<E, V> extends AbstractMap<E, V> {
    private static final int[] shifts = new int[10];
    private int size;
    private EHashMap.HashEntry<E, V>[] data;
    private int capacity;
    private Set<Entry<E, V>> entrySet;

    static {
      Random random = new Random(System.currentTimeMillis());
      for (int i = 0; i < 10; i++) {
        shifts[i] = 1 + 3 * i + random.nextInt(3);
      }
    }

    public EHashMap() {
      this(4);
    }

    private void setCapacity(int size) {
      capacity = Integer.highestOneBit(4 * size);
      //noinspection unchecked
      data = new EHashMap.HashEntry[capacity];
    }

    public EHashMap(int maxSize) {
      setCapacity(maxSize);
      entrySet =
          new AbstractSet<Entry<E, V>>() {

            public Iterator<Entry<E, V>> iterator() {
              return new Iterator<Entry<E, V>>() {
                private EHashMap.HashEntry<E, V> last = null;
                private EHashMap.HashEntry<E, V> current = null;
                private EHashMap.HashEntry<E, V> base = null;
                private int lastIndex = -1;
                private int index = -1;

                public boolean hasNext() {
                  if (current == null) {
                    for (index++; index < capacity; index++) {
                      if (data[index] != null) {
                        base = current = data[index];
                        break;
                      }
                    }
                  }
                  return current != null;
                }

                public Entry<E, V> next() {
                  if (!hasNext()) {
                    throw new NoSuchElementException();
                  }
                  last = current;
                  lastIndex = index;
                  current = current.next;
                  if (base.next != last) {
                    base = base.next;
                  }
                  return last;
                }

                public void remove() {
                  if (last == null) {
                    throw new IllegalStateException();
                  }
                  size--;
                  if (base == last) {
                    data[lastIndex] = last.next;
                  } else {
                    base.next = last.next;
                  }
                }
              };
            }

            public int size() {
              return size;
            }
          };
    }

    public EHashMap(Map<E, V> map) {
      this(map.size());
      putAll(map);
    }

    public Set<Entry<E, V>> entrySet() {
      return entrySet;
    }

    public void clear() {
      Arrays.fill(data, null);
      size = 0;
    }

    private int index(Object o) {
      return getHash(o.hashCode()) & (capacity - 1);
    }

    private int getHash(int h) {
      int result = h;
      for (int i : shifts) {
        result ^= h >>> i;
      }
      return result;
    }

    public V remove(Object o) {
      if (o == null) {
        return null;
      }
      int index = index(o);
      EHashMap.HashEntry<E, V> current = data[index];
      EHashMap.HashEntry<E, V> last = null;
      while (current != null) {
        if (current.key.equals(o)) {
          if (last == null) {
            data[index] = current.next;
          } else {
            last.next = current.next;
          }
          size--;
          return current.value;
        }
        last = current;
        current = current.next;
      }
      return null;
    }

    public V put(E e, V value) {
      if (e == null) {
        return null;
      }
      int index = index(e);
      EHashMap.HashEntry<E, V> current = data[index];
      if (current != null) {
        while (true) {
          if (current.key.equals(e)) {
            V oldValue = current.value;
            current.value = value;
            return oldValue;
          }
          if (current.next == null) {
            break;
          }
          current = current.next;
        }
      }
      if (current == null) {
        data[index] = new EHashMap.HashEntry<E, V>(e, value);
      } else {
        current.next = new EHashMap.HashEntry<E, V>(e, value);
      }
      size++;
      if (2 * size > capacity) {
        EHashMap.HashEntry<E, V>[] oldData = data;
        setCapacity(size);
        for (EHashMap.HashEntry<E, V> entry : oldData) {
          while (entry != null) {
            EHashMap.HashEntry<E, V> next = entry.next;
            index = index(entry.key);
            entry.next = data[index];
            data[index] = entry;
            entry = next;
          }
        }
      }
      return null;
    }

    public V get(Object o) {
      if (o == null) {
        return null;
      }
      int index = index(o);
      EHashMap.HashEntry<E, V> current = data[index];
      while (current != null) {
        if (current.key.equals(o)) {
          return current.value;
        }
        current = current.next;
      }
      return null;
    }

    public boolean containsKey(Object o) {
      if (o == null) {
        return false;
      }
      int index = index(o);
      EHashMap.HashEntry<E, V> current = data[index];
      while (current != null) {
        if (current.key.equals(o)) {
          return true;
        }
        current = current.next;
      }
      return false;
    }

    public int size() {
      return size;
    }

    private static class HashEntry<E, V> implements Entry<E, V> {
      private final E key;
      private V value;
      private EHashMap.HashEntry<E, V> next;

      private HashEntry(E key, V value) {
        this.key = key;
        this.value = value;
      }

      public E getKey() {
        return key;
      }

      public V getValue() {
        return value;
      }

      public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
      }
    }
  }

  static class RecursiveIndependentSetSystem implements IndependentSetSystem {
    private final int[] color;
    private final int[] rank;
    private int setCount;
    private IndependentSetSystem.Listener listener;

    public RecursiveIndependentSetSystem(int size) {
      color = new int[size];
      rank = new int[size];
      for (int i = 0; i < size; i++) {
        color[i] = i;
      }
      setCount = size;
    }

    public RecursiveIndependentSetSystem(RecursiveIndependentSetSystem other) {
      color = other.color.clone();
      rank = other.rank.clone();
      setCount = other.setCount;
    }

    public boolean join(int first, int second) {
      first = get(first);
      second = get(second);
      if (first == second) {
        return false;
      }
      if (rank[first] < rank[second]) {
        int temp = first;
        first = second;
        second = temp;
      } else if (rank[first] == rank[second]) {
        rank[first]++;
      }
      setCount--;
      color[second] = first;
      if (listener != null) {
        listener.joined(second, first);
      }
      return true;
    }

    public int get(int index) {
      int start = index;
      while (color[index] != index) {
        index = color[index];
      }
      while (start != index) {
        int next = color[start];
        color[start] = index;
        start = next;
      }
      return index;
    }

    public int getSetCount() {
      return setCount;
    }
  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void close() {
      writer.close();
    }

    public void printLine(long i) {
      writer.println(i);
    }

    public void printLine(int i) {
      writer.println(i);
    }
  }

  static interface IndependentSetSystem {
    interface Listener {
      void joined(int joinedRoot, int root);
    }
  }

  static class Counter<K> extends EHashMap<K, Long> {
    public Counter() {
      super();
    }

    public Counter(int capacity) {
      super(capacity);
    }

    public long add(K key) {
      long result = get(key);
      put(key, result + 1);
      return result + 1;
    }

    public Long get(Object key) {
      if (containsKey(key)) {
        return super.get(key);
      }
      return 0L;
    }
  }

  static class IntegerUtils {
    public static long power(long base, long exponent, long mod) {
      if (base >= mod) {
        base %= mod;
      }
      if (exponent == 0) {
        return 1 % mod;
      }
      long result = power(base, exponent >> 1, mod);
      result = result * result % mod;
      if ((exponent & 1) != 0) {
        result = result * base % mod;
      }
      return result;
    }
  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);
    }
  }
}
