Marinada '21

[lang=hr] Zadan je neusmjeren graf s $3n$ čvorova, označenih redom od $1$ do $3n$, pri čemu je $n = 100$. Svi bridovi iz prethodnog zadatka u lancu također su prisutni i u ovom grafu. Dodatno, postoje i bridovi između $n + k$ i $2n + k$ za sve prirodne brojeve $1 \leq k \leq n$. \\ Na koliko načina možemo svakom bridu odrediti usmjerenje tako da ne postoji usmjereni ciklus? Odgovor napišite modulo $1000000007$. [/lang] [lang=en] An undirected graph with $3n$ nodes is given, where $n = 100$. The nodes are labeled with integers from $1$ to $3n$. All of the edges from the previous problem are also present in the graph given here. Additionally, there is an edge between the nodes $n + k$ and $2n + k$ for every integer $1 \leq k \leq n$. \\ In how many ways can we assign a direction for each edge in such a way that there is no directed cycle in the graph? Write the answer modulo $1000000007$. [/lang]