Here, we assume that the values range from \(0\) to \(V-1\).

For each \(1 \leq k \leq V-1\), we count the ways ending up with \(k \leq a\). The answer is the sum of those numbers.

Now, consider a fixed \(k\). If we correspond values less than \(k\) to \(0\) and values not less than \(k\) to \(1\), we now have a problem with a \(01\)-sequence. By the way, the median of \((a,0,0)\) is \(0\), and that of \((a,1,1)\) is \(1\). Thus, if there is a time when the two values other than \(a\) are the same, the final value of \(a\) does not depend on the initial value (\(=A\)). Let us call these cases inactive, and the other cases active.

Here, from the symmetry of \(0,1\), the number of inactive cases with \(k=p\) resulting in \(0\) is equal to that of inactive cases with \(k=V-p\) resulting in \(1\). Eventually, considering only inactive cases for all \(1 \leq k \leq V-1\), exactly half of them print \(1\). Thus, we can easily handle the inactive cases.

Now, consider the active cases. Let \(G:=gcd(N,M)\). The active cases can be characterized as follows. (Here, the elements of \(x\) and \(y\) are converted to \(0,1\).)

• For each \(1 \leq r \leq G\), \(x_r=x_{r+G}=\cdots\) and \(y_r=y_{r+G}=\cdots\) and \(x_r \neq y_r\).

This follows from the fact that there is a time when \(x_i\) and \(y_j\) are used together \(\iff i \equiv j \bmod G\).

Eventually, the number of active cases can be found as \((k^{N/G}(V-k)^{M/G}+k^{M/G}(V-k)^{N/G})^G\). In these cases, the procedure does not change the value in input, so we just need to sum the aforementioned number for \(k \leq A\).

Implementation of the above solves the problem in \(O(V(\log N + \log M))\) time, which is fast enough.

Sample Solution(c++)