The exact number you want to compute is a fraction, with some factorials in the nominator and 2^(number of pairs that occur in both sequences). So, you can just pre-compute all the required factorials, and split each into a number of form o*(2^p), where o is an odd number modulo M and x >= 0. Then, you can handle separately all the odd prime factors (merged in o) and the power of 2.