Alien Neural Network

Let, Gi = (Vi, Ei) be the ith extension of the graph G0. The growth of this graph is highly exponential. Growth of Gi can be expressed with the following equations:

|Vi| = |Ei-1| * |Vi-1| - 2*|Ei-1| + |Vi-1|

|Ei| = |Ei-1|2

From the above equations, it is obvious that the nodes from a graph are preserved in its successive extensions. Now our problem is to find the maximum flow of the graph GN.

An observation: If a subgraph has only one incoming edge and only one outgoing edge outside the subgraph, then the subgraph can be replaced by an edge with the capacity equal to the maximum flow of the subgraph. For details, read about Closure. Now the whole graph GN can be compressed to G0 with appropriate edge capacities. Now, G1 can be compressed to G0 with each edges with capacity equal to maximum flow of G0. Let, maximum flow of G0 be f. Then, by applying the Max-flow min-cut theorem we can say, the maximum flow of the graph G1 is c*f, where c is the maximum edge-disjoint path. This compression of the extensions can be generalized by the following equation:

maximum flow of the graph Gi = maximum edge-disjoint path of Gi-1 * maximum flow of Gi-1. Now, if we can derive a relation between maximum edge-disjoint paths of the graphs Gi and Gi-1 we can solve the problem. The relation turns out to be similar as |Ei|. That is,

Maximum edge-disjoint path of Gi = (Maximum edge-disjoint path of Gi-1)2

And by doing the math one can find that,

Maximum flow of GN = cM*f, where M = 2N-1

Now, print the answer modulo 109+7 and remember to follow Euler's theorem.