A. Painel de Interruptores
Uma instalação possui R chaves de linha e C chaves de coluna. Cada chave pode ficar desligada (0) ou ligada (1). A lâmpada na interseção (i,j) fica acesa quando exatamente uma das duas chaves correspondentes está ligada; caso contrário, fica apagada.
Foram feitas Q observações de lâmpadas: cada uma exige que determinada lâmpada tenha estado b (0 apagada, 1 acesa). Pode haver observações repetidas da mesma lâmpada. Quantas configurações diferentes de todas as R+C chaves satisfazem as observações? Calcule o resultado módulo 1000000007.
Input
A primeira linha contém R C Q. Cada uma das próximas Q linhas contém i j b, com índices começando em 1.
Restrições:
1 ≤ R,C ≤ 200000; 0 ≤ Q ≤ 200000; 1 ≤ i ≤ R; 1 ≤ j ≤ C; b ∈ {0,1}; R+C ≤ 300000.
Output
Imprima a quantidade de configurações válidas módulo 1000000007.
Samples
Sample 1
Input
2 2 2 1 1 0 2 1 1
Output
4
As três chaves ligadas por observações possuem duas escolhas consistentes; a chave da segunda coluna é independente. Há quatro configurações.