Painéis sem origem

Time limit: 2000 msMemory limit: 256 MB

Um painel tem $n$ linhas e $m$ colunas. Cada célula deve ser pintada de branco ou preto, e exatamente $k$ células devem ser pretas.

O painel não tem uma origem marcada: deslocar todas as linhas ciclicamente pela mesma quantidade e todas as colunas ciclicamente pela mesma quantidade não altera o painel representado. Formalmente, duas pinturas $X$ e $Y$ são equivalentes se existem inteiros $a$ e $b$ , com $0\le a<n$ e $0\le b<m$ , tais que

$Y_{i,j}=X_{(i+a)\bmod n,\,(j+b)\bmod m}$

para todo $0\le i<n$ e $0\le j<m$ .

Não são permitidas rotações, reflexões, trocas de cores ou deslocamentos independentes de linhas ou colunas individuais.

Quantos painéis diferentes existem? Imprima a resposta módulo $1\,000\,000\,007$ .

Input

Uma linha com os inteiros $n$ , $m$ e $k$ .

$1\le n,m$ e $nm\le 200\,000$ .

Output

Um inteiro: a quantidade de classes de equivalência, módulo $1\,000\,000\,007$ .

Samples

Sample 1

Input

2 2 2

Output

As duas células pretas podem ocupar uma mesma linha, uma mesma coluna ou uma diagonal. As duas diagonais são equivalentes por um deslocamento; uma linha não é equivalente a uma coluna.

Sample 2

Input

1 4 2

Output

As células pretas podem ser vizinhas no ciclo ou estar em posições opostas.

Sample 3

Input

3 5 0

Output