How is it not $$$O(2^{n} n^{2})$$$ ?

A bit weird that the essential part of Hard is optimizing from obvious $$$O(2^{n} n^{2})$$$ (try all subsets and check if it is strongly connected) to anything faster (for example different $$$O(2^{n} n^{2})$$$).

CardboardBoxes:

So possible options of width + length are divisors of S / 2. We can find divisors of S / 2 in O(S).

While this is technically correct, a better bound (which matches the code below) is $$$O(\sqrt S)$$$. This is important because $$$S \leqslant 10^{13}$$$, so a linear solution would have timed out.

I have another incentive of Div1 250. Here, if we draw a net of a cardboard box, it's a complete rectangle!

For anyone struggling with Div 1 hard, particularly the latter part of the editorial:

Let's try to count the SCCs in the large graph and somehow connect that to the SCCs in the small (input) graph. I think of the nodes in the big graph arranged in the leaves of an imaginary N-ary tree (where N = b), with height k, so the path from the root to every leaf gives you the label for that leaf.

Property: Let L_u be the set of leaf nodes in the sub-tree of u. Then if v1 and v2 are siblings, from the standpoint of every node in L_v1, every node in L_v2 "looks the same" and vice versa. That means either everyone in L_v1 has directed edges to everyone in L_v2, or the same thing in the opposite direction.

Now take any subset of nodes in the large graph. We're going to reason about when this subset is an SCC. Metaphorically "select" the nodes from the subset, in the above N-ary tree. Now keep going up the tree until you reach the lowest common ancestor among all of the "selected" nodes. Take those children of this ancestor which lead to some selected leaf (i.e. which are themselves an ancestor of at least one selected node). Let's call this subset ANCESTORS. Remember the tree is a "B-ary" tree, therefore elements of ANCESTORS each are digits from 0 to b. Now the subset that you had selected is an SCC if and only if ANCESTORS is an SCC in the small graph: If ANCESTORS make an SCC in the small graph, with the property that the nodes in L_u "look the same" to L_v (with u and v being siblings), you can go from any L_a to any L_b (for a != b and a, b in ANCESTORS). For a = b we can do complete induction on the height of a node (with the base case of any single node being an SCC). If the selected nodes make an SCC, then there should be a way to go from all L_a's to L_b's (a, b in ANCESTORS). We know L_a is connected to L_b (=all nodes in L_a are connected to all nodes in L_b) in the large graph iff we a is connected to b in the small graph (from the problem statement). Therefore ANCESTORS is an SCC in the small graph.

Therefore all that matters is choosing subsets of nodes from the above tree, but keeping track of the set ANCESTORS each time. However as far as the counting is concerned, all of the ANCESTORS sets of the same size in the same level of the tree look the same: the moment you fix the elements of the ANCESTORS the SCC-ness is fixed.

Therefore whenever you find an SCC subset in the small graph, you'll ask "How many ANCESTORS sets are there in the graph with this many elements? Add that many to the total count of induced SCCs of the large graph".

One last thing which may be obvious: be careful when exponentiating 2 to a power which is itself a modulo'd power: a^(p — 1) = 1 mod p, therefore the behavior of the exponentiation of a repeats every p — 1 steps (rather than p). Therefore the exponent must be calculated modulo p — 1.