有一个城市公园,表示为一棵树,其顶点为 $$$n$$$ 景点,边缘为 $$$n - 1$$$ 铁轨。第 $$$i$$$ 个景点的幸福值为 $$$a_i$$$。
每个导轨都有一种颜色。如果 $$$t_i = 0$$$ 则为黑色,如果 $$$t_i = 1$$$ 则为白色。黑色列车仅在黑色铁轨上运行,白色列车仅在白色铁轨上运行。如果您以前乘坐过黑色火车,想乘坐白色火车,或者您以前乘坐过白色火车,想乘坐黑色火车,则需要使用 $$$1$$$ 车票。
游览的路径必须是简单的路径 - 不得多次访问某个景点。第一次登上火车时不需要车票。您只有 $$$k$$$ 车票,这意味着您最多只能转换 $$$k$$$ 次火车类型。特别是,您不需要车票即可通过由一种铁路颜色组成的路径。
将 $$$f(u, v)$$$ 定义为旅游 $$$(u, v)$$$ 中景点的幸福值总和,这是一条从第 $$$u$$$ 个景点开始,到第 $$$v$$$ 个景点结束的简单路径。求所有不需要超过 $$$k$$$ 门票的有效旅游 $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) 的 $$$f(u,v)$$$ 总和,模 $$$10^9 + 7$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n-1$$$) — 城市公园的景点数量和您拥有的门票数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 每个景点的幸福值。
接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$0 \leq t_i \leq 1$$$) — 之间的边顶点 $$$u_i$$$ 和 $$$v_i$$$ 颜色为 $$$t_i$$$。给定的边形成一棵树。
输出
输出一个整数,表示所有有效旅行 $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) 的总幸福值,模 $$$10^9 + 7$$$。
示例
输入 #1
5 0 1 3 2 6 4 1 2 1 1 4 0 3 2 1 2 5 0
输出 #1
45
输入 #2
3 1 1 1 1 1 2 1 3 2 0
输出 #2
10