Marinada '20

Promotrimo graf $G$ s vrhovima $\{1, 2, \ldots, 20000 \}$ takav da između svaka dva vrha postoji brid. 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.)