Problem Statement

多橋君は橋が大好きです。したがって、全ての辺が橋(グラフ理論用語)となる木と呼ばれるグラフが大好きです。また、多橋君は最近学校でXORについて学びました。そこで、次のような問題について考えています。

$N$ 頂点と $N-1$ 本の辺からなる連結な無向グラフ、つまり木が与えられます。各頂点は、それぞれ頂点 $1$、頂点 $2$、…、頂点 $N$ と呼ばれます。各辺にはそれぞれ非負整数のコストが割り振られています。

整数 $X$ が与えられるので、頂点 $a$ と頂点 $b$ を結ぶ単純パス(同じ辺を二度通らないパス、木においては必ず $1$ つだけ存在する)上の辺のコストの$\rm{xor}$和が $X$ になるような組 $(a,b)$ ($1≦a＜b≦N$)の総数を求めてください。 ただし$\rm{xor}$和とは、いくつかの整数 $A_1,A_2,…$ があったとき、それらの2進表現のビット毎の排他的論理和 $A_1$ $\rm{xor}$ $A_2$ $\rm{xor}…$ により得られる値のことを表します。 例えば、$1$ $\rm{xor}$ $2$ $\rm{xor}$ $5$ は $6$ です。

あなたの仕事は、多橋君の代わりにこの問題を解くことです。

Input

入力は以下の形式で標準入力から与えられる。

N X
x_1 y_1 c_1
x_2 y_2 c_2
:
x_{N-1} y_{N-1} c_{N-1}

• $1$ 行目には、グラフの頂点数を表す整数 $N (1 ≦ N ≦ 100,000)$ と問題文中の整数 $X (0≦X≦10^9)$ が与えられる。
• 続く $N-1$ 行には、グラフの $N-1$ 本の辺の情報が与えられる。このうち $i(1≦i≦N-1)$ 行目には、$i$ 番目の辺が結ぶ $2$ つの頂点 $x_i,y_i(1≦x_i,y_i≦N)$ とコスト $c_i (0≦c_i≦10^9)$ が与えられる。
• 与えられるグラフは連結であることが保証される。

Output

$1$ 行目に問題文中で求められている答えを出力せよ。末尾に改行を入れること。