Migrated from Lutece 1576 Icy Equat1on

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In mathematics, an equation is a statement of an equality containing one or more variables. Solving the equation consists of determining which values of the variables make the equality true.

Consider a magic equation as following:

where ``$\oplus$'' means the bitwise xor operation, and both $a$, $b$, $c$ are nonnegative integers.

Find the number of the triples $(a, b, c)$ which satisfy the above equation in the range of $0 \leq a \leq A$, $0 \leq b \leq B$, $0 \leq c \leq C$.

There are some examples about the bitwise xor operation for binary integers: $1 \oplus 1 = 0$, $0 \oplus 0 = 0$, $0 \oplus 1 = 1 \oplus 0 = 1$, $101 \oplus 011 = 110$.

In several programming languages, such as C, C++, Java, a caret ($^\wedge$) is used to denote the bitwise xor operator.

Input

One line contains three integers $A$, $B$, and $C$.

$0 \leq A, B, C \leq 10^{18}$.

Output

The number of the triples $(a, b, c)$ which satisfy the equation modulo $10^9 + 7$.

Samples

1 1 1

4

Note

Both $(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 0)$ satisfy the equation in the Sample.

Resources

The 15th UESTC Programming Contest Final