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