Во время грандиозного шоу иллюзионистов город из $n$ сцен соединён системой секретных ходов. Каждая сцена~--- это вершина, каждый ход между двумя сценами~--- это ребро.  Всего ходов $n-1$, и вместе они образуют дерево.

На каждом ребре написано число $w$~--- <<сила иллюзии>>, с которой зритель переносится между двумя сценами.

Рассмотрим любой маршрут шоу --- последовательность различных сцен $$u_1, u_2, \dots, u_k$$
где $k \geq 2$ и соседние сцены соединены прямым секретным ходом. Такой маршрут не может самопересекаться (одна и та же сцена не может появляться более одного раза). 

Красотой маршрута назовём XOR всех сил иллюзий на этом пути:

$$w_{u_1 \rightarrow u_2} \oplus w_{u_2 \rightarrow u_3} \oplus \dots \oplus w_{u_{k - 1} \rightarrow u_k}.$$

Организаторы шоу хотят знать, сколько существует различных маршрутов с заданной красотой иллюзии.