Consider a directed graph made from an orthogonal lattice of nodes. The edges are the horizontal and vertical connections between adjacent nodes. vertical directed lines are drawn and all the edges on these lines inherit that direction. Similarly, horizontal directed lines are drawn and all the edges on these lines inherit that direction.
Two nodes, and in a directed graph, are strongly connected if there is both a path, along the directed edges, from to as well as from to . Note that every node is strongly connected to itself.
A strongly connected component in a directed graph is a non-empty set of nodes satisfying the following two properties:
- All nodes in are strongly connected to each other.
- is maximal, in the sense that no node in is strongly connected to any node outside of .
There are ways of drawing the directed lines. Each way gives a directed graph . We define to be the number of strongly connected components in .
The illustration below shows a directed graph with and that consists of four different strongly connected components (indicated by the different colours).
Define to be the sum of for all possible graphs on a grid of . You are given , and .
Find giving your answer modulo .