题目描述

mhl 最近学习了《树》的概念

他觉得很有趣，于是自己画了一棵包含 $n$ 个节点的树，每条边的边长不一定相同，并且自己指定了一个节点 $p$ 为根节点

为了让这棵树更加有趣，mhl 把每条边设置成了有向边，这条边只允许从父亲走向儿子

现在 mhl 想知道，这棵树上有多少路径长度为 $k$ 的简单路径？

输入格式

输入第一行包含三个整数 $n,p,k$，如题意所示。

接下来 $n-1$ 行每行包含三个整数 $u,v,x$ ，表示节点 $u$ 和节点 $v$ 之间存在一条长度为 $x$ 的边。

输出格式

输出一行，该行包含一个整数，表示答案

数据范围

对于 $20\%$ 的数据: $10 \leq n \leq 100$。

对于 $50\%$ 的数据: $10 \leq n \leq 3000$。

对于 $100\%$ 的数据: $10 \leq n \leq 200000;1 \leq p \leq n;1 \leq x \leq 10^5;1 \leq k \leq 10^5$。

样例输入

5 2 2
2 1 2
2 3 1
3 4 1
3 5 1

样例输出

3