← 返回 microsoft 的题目列表Maximum XOR Product
类型：online_judge
Problem: Maximum XOR Product
Given three integers A, B, and N, find an integer X such that:
0 <= X < 2^N
and the following product is maximized:
(A XOR X) * (B XOR X)
Here XOR denotes the bitwise XOR operation.
Return the maximum product modulo 10^9 + 7.
Input Format
One line containing three integers:
A B N
Output Format
Print one integer, the maximum product modulo 10^9 + 7.
Constraints
0 <= N <= 30
1 <= A < 2^N
1 <= B < 2^N
Example 1
Input:
6 7 3
Output:
42
Example 2
Input:
10 25 5
Output:
420
Example
Input
1 2 2
Output
2