This problem can be solved with digit DP (Dynamic Programming).

Consider the following DP in that determines the lowest places to the higher of \(x_i\) in binary:

\(\mathrm{DP}[n][f_1][f_2][f_3][r_1][r_2][r_3]=\) the number of tuples of integers \((x_1,x_2,x_3)\) such that:

• \(0 \leq x_i < 2^n\) for each \(i\);
• \(x_1\oplus x_2\oplus x_3=0\);
• the truth value of “\(x_i\) is \(N\&(2^n-1)\) or less” is \(f_i\) for each \(i\); and
• the remainder of \(x_i\) divided by \(A_i\) is \(r_i\) for each \(i\).

Here, \(\&\) denotes bitwise AND; that is, \(N\&(2^n-1)\) denotes the value consisting of the least significant \(n\) digits of \(N\) in binary.

One can find \(\mathrm{DP}[n+1][*][*][*][*][*][*]\) from \(\mathrm{DP}[n][*][*][*][*][*][*]\) by trying the \(2^3\) combinations of \(n\)-th least significant digits of each \(x_i\) in binary.

In this constraints, \(N < 2^{60}\), so

\(\mathrm{DP}[60][\mathrm{True}][\mathrm{True}][\mathrm{True}][0][0][0]\) equals the number of tuples of integers \((x_1,x_2,x_3)\) such that:

• \(0 \leq x_i \leq N\) for each \(i\);
• \(x_1\oplus x_2\oplus x_3=0\);
• \(x_i\) is a multiple of \(A_i\) for each \(i\).

Since the \(1\)-st condition in the problem imposes \(1 \leq x_i \leq N\) for all \(i\), from the count above we need to subtract the number of tuples of integers \((x_1,x_2,x_3)\) such that:

• \(0 \leq x_i \leq N\) for any \(i\);
• \(x_1\oplus x_2\oplus x_3=0\);
• \(x_i\) is a multiple of \(A_i\) for each \(i\),

which can be easily found.

The complexity is \(O(\log N \prod A_i)\).