## Savings

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Sylva and Müko have a $$\mathbf{N} \times \mathbf{M}$$ chessboard which they use as a piggy bank. Rows are numbered from $$0$$ to $$\mathbf{N}-1$$ and columns -- from $$0$$ to $$\mathbf{M}-1$$. Sylva uses white cells for his savings while Müko uses black ones (the cell at row $$0$$ and column $$0$$ is white). Currently the cell at row $$r$$ and column $$c$$ contain $$r\ xor\ c$$ coins. Here $$xor$$ is a bitwise exclusive or operation.

Because of coronavirus in order to make a living the guys have to take $$\mathbf{K}$$ coins out of each board cell (if a cell contains less than $$\mathbf{K}$$ coins they take everything from it). Then they need to calculate a savings balance which is a difference between the number of Sylva's coins and the number of Müko's coins. Your task is to help them to find the balance value modulo $$1000000007\ (10^9+7)$$.

#### Input

The only line contains three integers $$\mathbf{N}$$, $$\mathbf{M}$$, and $$\mathbf{K}$$.

• $$1 \le \mathbf{N}, \mathbf{M} \le 10^{18}$$,
• $$0 \le \mathbf{K} \le 10^{18}$$.

#### Output

The savings balance modulo $$1000000007$$.

#### Examples

Input 1:

5 3 3

Output 1:

2