Marinada '20

Promotrimo graf $G$ s vrhovima $\{1, 2, \ldots, 20000 \}$ i bridovima $\{ \{1,2\}, \{2,3\}, \ldots, \{19999, 20000\}\}$. Svaki od vrhova obojan je u crno ili u bijelo. Za bojanje kažemo da je \emph{ekvilibrij} od $G$ ako ne postoji vrh kojem možemo promijeniti boju, a da povećamo broj bridova koji spajaju raznobojne vrhove. Koliko različitih ekvilibrija od $G$ postoji? (Napišite samo zadnjih $6$ znamenaka odgovora.)