B"The United Federation of Planets is an alliance of N planets, they are indexed from 1 to N . Some planets are connected by space tunnels. In a space tunnel, a starship can fly both ways really fast. There are exactly N-1 space tunnels, and we can travel from any planet to any other planet in the Federation using these tunnels. It's well known that there are D additional parallel universes. These are exact copies of our universe, they have the same planets and space tunnels. They are indexed from 1 to D (our universe has index 0 ). We denote the planet x in universe i by P_x^i . We can travel from one universe to another using dimension portals. For every i ( 0 <= q i <= q D-1 ), we will place exactly one portal that allows us to fly from P_{A_i}^i to P_{B_i}^{i+1} , for some planet indices A_i and B_i (i.e. 1 <= q A_i, B_i <= q N ). Once all the portals are placed, Starship Batthy xc3 xa1ny will embark on its maiden voyage. It is currently orbiting around P_1^0 . Captain xc3 x81gnes and Lieutenant G xc3 xa1bor have decided to play the following game: they choose alternately a destination (a planet) to fly to. This planet can be in the same universe, if a space tunnel goes there, or it can be in another universe, if a portal goes there. Their aim is to visit places where no one has gone before. That's why, once they have visited a planet P_x^i , they never go back there (but they can visit the planet x in another universe). Captain xc3 x81gnes chooses the first destination (then G xc3 xa1bor, then xc3 x81gnes etc.). If somebody can't choose a planet where they have not been before in his/her turn, he/she loses. Captain xc3 x81gnes and Lieutenant G xc3 xa1bor are both very clever: they know the locations of all tunnels and portals, and they both play optimally. For how many different placements of portals does Captain xc3 x81gnes win the game? Two placements are different if there is an index"...