Permutation Oddness

The first thing to do is throw away the fake complexity. There are only four values, and lowbit makes the adjacency cost very rigid:

• same value: contributes 0
• different values with the same parity, so 0 with 2 or 1 with 3: contributes 2
• different parity: contributes 1

So split the values into two parity groups:

• red: {0,2}
• blue: {1,3}

Every red-blue adjacent pair contributes exactly 1. Inside red, only a 0/2 switch contributes, and it contributes 2. Inside blue, only a 1/3 switch contributes, also 2.

That is the whole problem. The rest is just counting without faceplanting into overcounting.

Blocks

Look at a final permutation and merge consecutive red values into red blocks, and consecutive blue values into blue blocks. The colors of blocks must alternate.

If there are r red blocks and b blue blocks:

• r=b: there are two possible color skeletons, starting with red or starting with blue. The number of color boundaries is 2r-1.
• r=b+1: the skeleton must start and end with red. The number of boundaries is 2b.
• b=r+1: the skeleton must start and end with blue. The number of boundaries is 2r.
• otherwise it is impossible.

Those boundaries already give that many points of oddness. The internal parts of the blocks are independent between red and blue.

Define R[s][u] as the number of ways to split all c0 zeros and c2 twos into s ordered nonempty red blocks such that, inside those red blocks, there are exactly u adjacent switches between 0 and 2.

Each such switch contributes 2, so the red internal contribution is 2u. Define B[s][u] the same way for 1 and 3.

Then combining is direct:

• for equal block counts s, add R[s][u] * B[s][v] * 2 to oddness 2(u+v) + (2s-1)
• for red having one fewer block than blue, add R[s][u] * B[s+1][v] to oddness 2(u+v) + 2s
• for red having one more block than blue, add R[s+1][u] * B[s][v] to oddness 2(u+v) + 2s

The factor 2 in the equal case is just the two possible starting colors. No magic, just alternating blocks.

Computing one table

Now solve the generic subproblem:

Given x copies of one symbol and y copies of another symbol, count ways to split them into ordered nonempty blocks, grouped by number of blocks and number of internal switches.

Take the ordered blocks and concatenate them. You get one binary string with x copies of the first symbol and y copies of the second. The block split is then exactly a choice of cut positions between adjacent characters of this string. This is a bijection, so it counts every possibility once.

Suppose the binary string has L runs. Example: 000222002 has 4 runs. Then:

• switch adjacencies: D = L-1
• equal adjacencies: S = x+y-L

First count how many binary strings have L runs.

If L is even, both symbols have L/2 runs, and there are two choices for the starting symbol. So the count is

2 * C(x-1, L/2-1) * C(y-1, L/2-1).

If L is odd, one symbol has (L+1)/2 runs and the other has L/2 runs. Either symbol can be the one with more runs, so we add both cases:

C(x-1, (L+1)/2-1) * C(y-1, L/2-1)

and

C(x-1, L/2-1) * C(y-1, (L+1)/2-1).

Why these binomials? Splitting x identical items into a positive run lengths is C(x-1,a-1). Same for y. Standard bars-and-stars, nothing cursed.

Now choose cuts.

Among the D switch adjacencies, choose p to cut. Among the S equal adjacencies, choose q to cut. Then:

• number of blocks becomes p+q+1
• internal switches left inside blocks becomes D-p

So for each valid run-count case, we add

ways_for_strings * C(D,p) * C(S,q)

to

table[p+q+1][D-p].

That builds the table in O(len^3) for one parity group.

Final algorithm

1. Precompute binomial coefficients modulo 1e9+7 up to 800.
2. Build the red table from (c0,c2).
3. Build the blue table from (c1,c3).
4. Combine red and blue tables using the alternating-block cases above.

The total complexity is O(n^3) per large test shape, and the sum of n is at most 800, so this is fine. A 2900 problem, yes, but the core trick is clean: parity blocks first, run cuts second.