First calculate d[i][j], 1 <= i <= 20, 1 <= j <= N — how many numbers from A[1] .. A[j] have i'th bit set.

Now for each query (K, P, R) look at each 20 bits of K (20 because numbers do not exceed 10^6).

Calculate the following:

for (int i = 0; i < 20; ++i) {
	LL z1 = d[i][r] - d[i][p - 1]; //how many numbers from A[p] .. A[r] have i'th bit set
	LL z0 = r - p + 1 - z1; //how many numbers in A[p] .. A[r] have i'th bit not set
	if (k & (1 << i)) //if K has i'th bit set, only count pairs in A[p] .. A[r] where both bits are not set or both bits are set, multiply the count by 2^i
		answer = (answer + ((LL)1 << i) * (z0 * (z0 - 1) + z1 * (z1 - 1)) / 2) % MOD;
	else //else count pairs where one bit is set and one is not
		answer = (answer + ((LL)1 << i) * z0 * z1) % MOD;
}