XOR Coloring

Problem Overview

• Given an array A of N integers; each element can be colored white, black, or left uncolored.
• Let x be XOR of whites and y be XOR of blacks; count colorings where x and y > 0 and either x is a multiple of y or y is a multiple of x.
• Input: N then N values; Output: number of good colorings modulo 1e9+7.
• Constraints: 1 ≤ N ≤ 1e5, 1 ≤ A[i] ≤ 1e5; domain: arrays, bitwise XOR, combinatorics.
• From Microsoft interviews; a coding interview question and interview question on XOR counting problem.