Simulating the process is fast enough.

Very simple greedy algorithm.

We focus on the first permutation and divide it in contiguous maximum length blocks that appear in that order in all other permutations, we can do this in O(nm) if we make the first permutation $$$1,2,3,\dots ,n$$$ and adjust all others accordingly. I didn't think of this and used map, it barely passed at 997ms

I liked this one! We use meet in the middle to calculate all possible sums $$$\pmod{m}$$$ of each half. Since our sums are between $$$0,m-1$$$ for any left sum $$$S_i$$$ the best we can choose in the right is the largest number $$$\le m-1-S_i$$$, or the largest right sum since the total is $$$<2m$$$. Thus, we do a binary search :)

Since the numbers are $$$\le 10^4$$$ it's faster to count how many we have in that range. We save all the numbers whose sum of digits in binary is $$$k$$$ beforehand, and for each $$$i < 10^4$$$ we xor it with all of them to calculate the numbers $$$j$$$ that are at distance $$$k$$$ from $$$i$$$. So at each step we add to the answer $$$am[i]*am[j]$$$. There are $$$\le \dbinom{14}{7} = 3432$$$ numbers at distance $$$k$$$ so this is fast enough.