Oh I found such a submission. I only thought of solutions for S=2k,3k,3k+2, but there's a simple solution for S=2k+1.

In fact only one in-contest submission used extended gcd while the other 12 are $$$O(T)$$$

Because ans may not be even before you divide by 2. Correct answer is floor(ans/2).

Overflow probably

It's wrong. You don't divide by k, you multiple by B then divide by 2. You also have to make sure if the number is odd before dividing by 2. This is doable by checking if all the numbers you're multiplying are odd

I will try to explain my $$$O(n^2)$$$ solution, which is independent of $$$k$$$ in the problem. The editorial lists a different $$$O(n(k+\log n))$$$ solution.

My solution relies on the following observation, for fixed permutation $$$p$$$ applied to the array of values $$$A$$$:

There exists an MST where for each index $$$j \gt 1$$$ , there is an edge from $$$j$$$ to the index with the minimum value (after having applied the $$$p$$$ to $$$A$$$) among $$$A[j-k], A[j-k+1] \dots A[j-1]$$$.

To prove it, you can apply induction and in the inductive step, we can apply an exchange argument that relies on the fact that in the MST, the suffix from $$$j$$$ will be connected to the prefix before $$$j$$$. So you can apply the exchange argument according to which edge from the suffix component you remove and replace with the edge from $$$j$$$ to its prefix.

After this observation, the problem becomes simple: fix index $$$j$$$ and value of element $$$i$$$, and then count how many arrays exist with $$$max(A[j], min(A[j-k], A[j-k+1] \dots A[j-1])) = i $$$.

Submission