20279번 - Dança da Divisibilidade 다국어

No país da Nlogônia os habitantes realizam uma dança especial para homenagear o deus da divisibilidade.A dança é executada por N homens e N mulheres dispostos em dois círculos. Os homens ficam no círculo interno e as mulheres no círculo externo. Cada mulher inicia de frente para um homem.

A dança é composta de K movimentos; homens e mulheres se alternam nos movimentos, começando com os homens. No i-ésimo movimento, as pessoas do círculo correspondente rotacionam P_i passos em sentido horário enquanto as pessoas do outro círculo permanecem paradas. Assim, cada pessoa troca de parceiro para um que está a P_i posições de distância. Um movimento é válido se os parceiros de cada pessoa são diferentes ao início e ao fim do movimento e, além disso, nenhum par de pessoas está frente a frente em dois instantes de tempo distintos.

Como forma de homenagem, as danças sempre precisam terminar com casais cujas somas das idades tenham o mesmo resto quando dividido pelo número sagrado M. Ou seja, se a soma das idades de um casal deixa um resto R quando divido por M, então a soma das idades de todos os casais devem deixar o mesmo resto R ao fim da dança.

Fornecidos N, M e K e as idades de todos os dançarinos, determine de quantas formas se pode realizar a dança. Como a idade dos dançarinos é medida em segundos, os valores podem ser muito grandes.

A primeira linha da entrada contém três inteiros N (3 ≤ N ≤ 10⁶), M (1 ≤ M ≤ 10⁹) e K (1 ≤ K ≤ 10⁹), correspondendo à quantidade de pessoas em um círculo, ao número sagrado e à quantidade de movimentos da dança, respectivamente.

A segunda linha da entrada contém N inteiros A_i (1 ≤ A_i ≤ 10⁹) separados por um espaço em branco e representando a idade das mulheres.

A terceira linha da entrada contém N inteiros B_i (1 ≤ B_i ≤ 10⁹) separados por um espaço em branco e representando a idade dos homens.

Inicialmente o i-ésimo homem está alinhado com a i-ésima mulher, e o primeiro elemento de cada vetor é considerado à direita do respectivo último elemento.

A saída consiste de um único inteiro representando o resto da divisão do número de danças distintas por 10⁹ + 7.