For some "monotone" bottom left part, we will have the first type, and for the top right part, we will have the second type. We can do some sort of DP to count the number of possibilities to have a path divide the grid from top left to bottom right. If e is the number of empty cells and the path has c corners, then there are 2^(e-c) ways to set the cells. Our DP should sum up 2^-c over all paths.

Iterate over all p^k <= n, where p is a prime. Let dp0[i] = number of permutations of length i not containing any cycle with a length which is a multiple of p^k and dp1[i] = number of permutations which do contain such a cycle. The DP is calculated in a way similar to calculating the number of partitions. It can be sped up with prefix sums. Multiply the answer by p^dp1[n].

We can obviously fix k nodes to be the nodes of the starting state. It turns out that the operations we can perform are swapping pairs of nodes in the starting state (who knows how to prove). If we can swap u and v, then let's add an edge between u and v. The answer can be calculated by finding the sizes of the components in the new graph.

To speed it up, we can't choose any k nodes, or else we might end up with O(n^2) edges. gamegame used the first k in preorder, I used the first k in postorder. In both cases, only O(n) edges need to be constructed. If we sweep through k, each edge will be active in a range. I used dynamic connectivity to maintain the sizes of the components and the answer. gamegame was able to do something with just dsu that I don't understand. orz.

Consider how is the top-left corner (1, 1) fertilized. Let's first consider the case where the top-left square is fertilized by a sweet corn sprinkler. Clearly, in order to do so, there must exist a corn sprinkler somewhere in the first row. Let's consider the rightmost such sprinkler in the first row; that is, the corn sprinkler with coordinates (1, x) where x is maximized.

Notice that the rectangular region with corners (1, 1) and (n, x), which we will call the "sprinkled region", are all sprinkled by this corn sprinkler; therefore, no alfalfa sprinkler can be installed in the sprinkled region. Also, we can pick any arbitary subset of free squares in the sprinkled region to install corn sprinklers in, without violating any requirements of the problem; the only requirement is that (1, x) must have a corn sprinkler. Also notice that this sprinkled region and the non-sprinkled region are independent from each other, as no alfalfa sprinkler in the non-sprinkled region can sprinkle any part of the sprinkled region (corn sprinklers in the non-sprinkled region can sprinkle parts of the sprinkled region, but that does not matter because no conflict will occur), and the range of a sweet corn sprinkler within the sprinkled region will never go outside the sprinkled region.

We can, using a similar method, analyze the case where the top-left corner is sprinkled by an alfalfa sprinkler.

Observe that the non-sprinkled region is a smaller version of the original problem, and any combination of a plan for the non-sprinkled region with a plan for the sprinkled region is valid (as the 2 regions are independent from each other); therefore, the problem can be solved with dynamic programming.

Define f[i][j][k] to be the number of ways to set sprinklers in the rectangular region with corners (i, j) and (n, n) (in other words, all squares to the bottom-right of (i, j)). k = 0 indicates that (i, j) is sprinkled by a corn sprinkler and k = 1 indicates that (i, j) is sprinkled by an alfalfa sprinkler.

Let's also define psum(i, j) as the number of free squares (x, y) where x >= i and y >= j. The array can easily be precomputed in O(n^2) time.

When k = 0, enumerate the location of the rightmost corn sprinkler on row i, which is (i, x) where x >= j. Therefore:

f[i][j][0] = sigma f[i][x+1][1] * 2^(psum(i, j) — psum(i, x+1) — 1) for all x >= j where (i, x) is a free square. The expression psum(i, j) — psum(i, x+1) — 1 refers to the number of squares where we can decide whether to install a corn sprinkler. We use f[i][x+1][1] (that is, require (i, x+1) to be sprinkled by an alfalfa sprinkler) because if (i, x+1) is sprinkled by a corn sprinkler, it would violate the assumption that (i, x) is the rightmost corn sprinkler on row i.

Similarly, when k = 1, enumerate the location of the bottommost alfalfa sprinkler on column j, which is (x, j). Therefore:

f[i][j][1] = sigma f[x+1][j][0] * 2^(psum(i, j) — psum(x+1, j) — 1)

The final answer is f[1][1][0] + f[1][1][1].

This DP is O(n^3); to speed it up to O(n^2) we first take the factor 2^psum(i, j) out of the summation. Then the DP can be optimized with suffix sums of the values of f[x][y][1] * 2^(-psum(x, y)-1) for each row, and the values of f[x][y][0] * 2^(-psum(x, y)-1) for each column.

Approximate difficulty of this problem is Div1C — Div1D.

Observe that for any permutation, its step count (number of steps before returning to original) is equal to the LCM of the sizes of all its cycles.

For example, the permutation (2, 3, 1, 5, 4, 6) has three cycles: (1, 2, 3), (4, 5), and (6). Its step count is LCM(3, 2, 1) = 6.

Define cnt(p^k) (where p is a prime number) as the number of permutations of length n that contain at least one cycle whose size is a multiple of p^k.

Consider the contribution of each prime power to the answer.

The number of permutations whose step count contains a factor p^k but not any higher power of p is clearly cnt(p^k) — cnt(p^(k+1)). Thus, the answer is the product of (p^k)^(cnt(p^k) — cnt(p^(k+1))) for all p^k <= n.

The only remaining problem is finding a way of quickly computing cnt(p^k). Notice that since we are computing a value that goes into the exponent, we must compute cnt(p^k) modulo phi(M). Since M is guaranteed to be prime, phi(M) is always M-1.

Let's compute cnt(p^k) by first computing the number of permutations that do NOT contain a cycle whose size is a multiple of x. At the end, subtract this value from n! to obtain the value of cnt(p^k).

We calculate these values using dynamic programming, by building the permutation one cycle at a time. To prevent double-counting due to cycles being inserted in different orders, we require that each cycle inserted include the leftmost element that currently does not belong in a cycle. Clearly, after adding this restriction, each permutation can be constructed in exactly one way.

Define f[i] as the number of partially built permutations, where i out of the n elements have been determined (by insertion into a cycle). The value of f[n] is what we need.

To find out the value of f[i], we use the following formula:

f[i] = sigma C(n-(i-x)-1, x-1) * f[i-x] * (x-1)!

Where x is the size of the newly inserted cycle; it can be any positive integer that is not greater than i and also not a multiple of p^k.

Explanation: C(n-(i-x)-1, x-1) is the number of different sets of positions the new cycle could occupy (the -1's are there to satisfy the constraint of always choosing the leftmost unused element, described above). (x-1)! is the number of ways to arrange the x elements into a cycle.

This DP takes O(n^2) time to compute one value of cnt. To speed it up, we first try expanding C(n-(i-x)-1) into factorials. We notice that the (x-1)! cancels out.

f[i] = sigma (n-(i-x)-1)! * f[i-x] / (n-i)!

It looks like that we could simply maintain a sum of all previous values of (n-a-1)! * f[a] for all 1 <= a < i, subtract the values associated with unacceptable cycle sizes (those that are multiples of p^k), and divide by (n-i)! at the end. Unfortunately, since our modulo is not prime (see earlier discussion of subtracting M by one), we cannot divide by (n-i)!.

So, instead of trying to maintain a sum that does not contain the division by (n-i)!, we keep this division in our "current sum" variable. Each time we move forward one element, from i to i+1, we multiply the current sum by n-i (so that the division by (n-i)! becomes (n-(i+1))!), and then add the value of (n-i-1)!f[i] / (n-(i+1))!, which simplifies to just f[i], into the current sum. When computing a value of f[i], we simply use the current sum, then subtract the number of possibilities associated with cycles with sizes that are multiples of p^k.

The time complexity of calculating each cnt(p^k) is now O(n^2/p^k), as each f[i] is computed in O(n/p^k). The time complexity of the entire problem is therefore O(an^2), where a is the sum of the reciprocals of all the prime powers under n. We know that the sum of the reciprocals of the primes under n is O(loglogn). The addition of powers of these reciprocals to the sum will multiply the sum by at most 2, as 1/p + 1/p^2 + 1/p^3 + ... = 1/p-1, which is less than or equal to 2/p for all p >= 2. Therefore, we can conclude that a is also O(loglogn). (Let me know if there is an error in this logic.)

The final time complexity is O(n^2loglogn). Use the provided Barrett reduction code to reduce constant factors in the solution.

Approximate difficulty of this problem is Div1D — Div1E.