給你三個整數 a ，b 和 n ，請你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要滿足 0 <= x < 2n。

由于答案可能會很大，返回它對 109 + 7 取余 后的結果。

注意，XOR 是按位異或操作。

示例 1：

輸入：a = 12, b = 5, n = 4
輸出：98
解釋：當 x = 2 時，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。
98 是所有滿足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。
示例 2：

輸入：a = 6, b = 7 , n = 5
輸出：930
解釋：當 x = 25 時，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。
930 是所有滿足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。
示例 3：

輸入：a = 1, b = 6, n = 3
輸出：12
解釋： 當 x = 5 時，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。
12 是所有滿足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

提示：

0 <= a, b < 250
0 <= n <= 50

class Solution {public int maximumXorProduct(long a, long b, int n) {if(a < b) {a = a ^ b;b = a ^ b;a = a ^ b;}long MOD = (int)1e9+7;long mask = (1L<<n)-1; // n個1long ax = a & ~mask; // 沒辦法通過 xor x 修改的部分long bx = b & ~mask;a &= mask; // 保留低于n的比特位b &= mask;long left = a ^ b; // 一個是0 一個是1 的比特位long one = mask ^ left; // 全為 1 或者 全為0 的比特位ax |= one; // 異或結果一定是1先加到結果bx |= one;if(left > 0 && ax == bx) {// left 的最高位給ax 其余給bxlong high_bit = 1L << (63 - Long.numberOfLeadingZeros(left));ax |= high_bit;left ^= high_bit;}bx |= left;return (int) (ax % MOD * (bx % MOD) % MOD);}
}