Maximum Xor Product
Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2^n.
Since the answer may be too large, return it modulo 10^9 + 7.
Note that XOR is the bitwise XOR operation.
Example 1
Input
a = 12, b = 5, n = 4Output
98For
x = 2, (a XOR x) = 14 and (b XOR x) = 7, so the maximum product is 98.Example 2
Input
a = 6, b = 7, n = 5Output
930For
x = 25, (a XOR x) = 31 and (b XOR x) = 30, so the maximum product is 930.Constraints
- 0 <= a, b < 2^50
- 0 <= n <= 50