Beto y Carlos discuten acerca de una extraño objeto que se encontraron mientras caminaban. Beto afirma que se trata de un grafo conexo sin ciclos, Carlos por su parte dice que es un grafo que cumple que entre cada par de nodos existe un camino simple y es único. Alicia que por allí pasaba observando la naturaleza, decide ponerle fin a su disputa, ella que es bien versada en la biología les dice que se trata de un árbol y por supuesto, ¡todos los árboles tienen hormigas!.

Alicia se siente curiosa acerca de estas hormigas y nota que una hormiga viaja de un nodo ~u~ a un nodo ~v~ solo si el XOR de las aristas en el camino de ~u~ a ~v~ es igual a ~k~. Alicia está tratando de descubrir por que las hormigas hacen esto y ella cree que contar la cantidad de caminos distintos que la hormigas pueden tomar le ayudará a descubrirlo, por desgracia Alicia no sabe mucho de matemática y no confía mucho en Carlos y Beto dado que ni si quiera pueden reconocer un árbol frente a sus narices. Ayuda a Alicia a resolver su problema.

Formalmente dado un árbol con ~n~ nodos y ponderado(con pesos en las aristas) cuente la cantidad de pares ~u,v(u<v)~ tal que el XOR de los pesos de las aristas en el camino simple de ~u~ a ~v~ es igual a ~k~.

Subtareas:

• Cada nodo tiene degree a lo sumo 2 (el árbol forma una cadena de nodos consecutivos).(10 Puntos)
• ~2 \leq n \leq 500~.(10 Puntos)
• ~2 \leq n \leq 5000~.(20 puntos)
• ~0\leq k \leq 2^8-1~ y ~0\leq c_i \leq 2^8-1~ para toda arista ~i~ ~(1\leq i \leq n-1)~.(20 puntos)
• ~k=0~.(30 puntos)
• Sin restricciones adicionales.(10 puntos)

Entrada

La primera línea contiene dos enteros ~n,k~ ~(2 \leq n \leq 2\cdot 10^5, 0\leq k \leq 2^{30} -1)~. Luego le siguen ~n-1~ líneas con la descripción de las aristas,las aristas vienen dadas de la forma ~u_i,v_i,c_i~ ~(u\neq v)~ lo que significa que hay una arista no dirigida entre el nodo ~u_i~ y el nodo ~v_i~ con peso ~c_i~ ~(0\leq c \leq 2^{30} -1)~. Te garantizamos que las aristas forman un árbol.

Salida

Usted debe devolver un único número, la cantidad de pares ~u,v(u<v)~ tal que el XOR de los pesos de las aristas en el camino simple de ~u~ a ~v~ es igual a ~k~.

Ejemplo de entrada #1

7 0
1 2 2
2 4 1
1 3 3
1 6 1
6 5 0
6 7 3

Ejemplo de salida #1

3

Ejemplo de entrada #2

6 9
1 5 1
3 5 12
3 6 5
4 6 15
4 2 3

Ejemplo de salida #2

2

En el primer ejemplo los caminos que cumplen la condición son (3,4),(2,7) y (5,6).

Nota

El XOR bit a bit de enteros no negativos ~A~ y ~B~, ~A \oplus B~ , se define de la siguiente manera: Cuando ~A \oplus B~ se escribe en base dos, el dígito en el lugar de ~2^k~ ~(k \geq 0)~ es ~1~ si exactamente uno de los dígitos en ese lugar de ~A~ y ~B~ es ~1~, y ~0~ en el caso contrario. Por ejemplo, tenemos ~3\oplus 5 = 6~ (en base dos: ~011 \oplus 101 = 110~). Generalmente, el XOR bit a bit de ~k~ enteros no negativos ~p_1,p_2,p_3, \dots ,p_k~ se define como ~(\dots ((p_1 \oplus p_2)\oplus p_3)\oplus \cdots \oplus p_k)~. Podemos demostrar que este valor no depende del orden de ~p_1,p_2,p_3,\dots ,p_k~. Esta operación se hace mediante el símbolo ^ en muchos lenguajes de programación.