この問題は桁DPにより解くことができます。

\(x_i\) を二進法で表したときの下の桁から決める次のような桁DPを考えます。

\(\mathrm{DP}[n][f_1][f_2][f_3][r_1][r_2][r_3]=\) 以下の条件を全て満たす整数の組 \((x_1,x_2,x_3)\) の個数

• 全ての \(i\) で \(0 \leq x_i < 2^n\)
• \(x_1\oplus x_2\oplus x_3=0\)
• 各 \(i\) で、「\(x_i\) が \(N\&(2^n-1)\) 以下である」の真偽が \(f_i\)
• 各 \(i\) で、\(x_i\) を \(A_i\) で割ったあまりが \(r_i\)

ただし、\(\&\) は bit ごとの and を表すものとします。つまり、\(N\&(2^n-1)\) は \(N\) を二進法で表したときの下 \(n\) 桁からなる値を表します。

各 \(x_i\) の二進法で下から \(n\) 桁目の値を \(2^3\) 通り試すことで、\(\mathrm{DP}[n][*][*][*][*][*][*]\) から \(\mathrm{DP}[n+1][*][*][*][*][*][*]\) を求めることができます。

今回の制約では \(N < 2^{60}\) であることから、

\(\mathrm{DP}[60][\mathrm{True}][\mathrm{True}][\mathrm{True}][0][0][0]\) は、

• 全ての \(i\) で \(0 \leq x_i \leq N\)
• \(x_1\oplus x_2\oplus x_3=0\)
• 各 \(i\) で、\(x_i\) は \(A_i\) の倍数

を全て満たす整数の組 \((x_1,x_2,x_3)\) の個数となります。求める答えは \(1\) 番目の条件が「全ての \(i\) で \(1 \leq x_i \leq N\)」であったことから、ここから

• いずれかの \(i\) で \(x_i=0\)
• \(x_1\oplus x_2\oplus x_3=0\)
• 各 \(i\) で、\(x_i\) は \(A_i\) の倍数

を全て満たす整数の組 \((x_1,x_2,x_3)\) の個数を引く必要があります。これは容易に求めることができます。

計算量は \(O(\log N \prod A_i)\) となります。