식스팩

광택 나는 세련된 잡지 National Gentlemen and Ladies Beer Magazine은 주로 젊은 IT 전문가들을 대상으로 매달 콘테스트를 연다. 이들은 물론 이 잡지의 주된 구독자이기도 하다. 콘테스트는 잡지 첫 페이지에 세련된 맥주 거품 배경 위에 인쇄된 이른바 식스팩 퍼즐을 바탕으로 한다. 퍼즐은 두 개의 행과 세 개 이상의 열로 이루어진 직사각형 격자로 구성된다. 격자의 일부 칸은 비어 있고, 일부 칸에는 한 자리 십진수가 들어 있으며, 서로 다른 칸에는 서로 다른 숫자가 들어 있을 수 있다. 극단적인 경우 격자가 완전히 비어 있거나 완전히 채워져 있을 수도 있다. 격자에서 연속한 세 개의 열을 식스팩이라고 부르며, 퍼즐의 이름도 여기에서 나왔다.

격자와 함께 정수 K가 주어지며, 이 또한 퍼즐의 일부이다.

독자의 과제는 격자의 빈 칸마다 한 자리 숫자를 채워, 각 식스팩에 있는 값의 합이 K가 되도록 하는 것이다. 서로 다른 칸에는 서로 다른 숫자가 들어가도 된다. 그다음 독자는 자신의 퍼즐 해답을 잡지의 자문 위원회에 보낸다. 위원회는 접수한 모든 해답을 기록한다. 독자의 해답이 위원회가 이전에 받은 어떤 해답과 같으면 그 독자는 상을 받지 못한다. 독자의 해답이 지금까지 위원회가 받은 모든 해답과 다르면, 그 독자는 좋은 맥주 브랜드의 진짜 맥주 식스팩 한 묶음을 받는다. 묶음에 들어 있는 식스팩의 수는 위원회가 독자의 해답을 받은 직후 위원회가 보유한 서로 다른 퍼즐 해답의 수와 같다.

두 해답은 격자에서 같은 위치에 있는 칸의 내용이 적어도 하나 다르면 서로 다른 것으로 본다.

독자는 해답을 많아야 한 번 보낼 수 있다. 같은 독자가 추가로 보낸 해답은 항상 무시된다. 위원회의 비서는 위원회가 같은 순간에 두 개 이상의 해답을 받는 일은 없다고 보증한다.

주어진 식스팩 퍼즐에 대해, 잡지 독자가 해당 콘테스트에서 받을 수 있는 맥주 식스팩의 최대 개수를 계산하시오. 이 잡지는 워낙 인기가 많아서 잡지 독자의 수가 퍼즐의 서로 다른 해답 수보다 많다고 확신할 수 있다.

입력은 식스팩 퍼즐 하나를 지정한다. 첫째 줄에 세 정수 N (3 ≤ N ≤ 105), K (0 ≤ K ≤ 100), M (0 ≤ M ≤ 2 · 105)이 주어진다. N은 격자의 열 수이고, K는 각 식스팩에서 요구되는 합이며, M은 격자에 미리 정해진 값의 개수이다. 다음 M개 줄 각각에는 세 정수 C (0 ≤ C ≤ N − 1), R (0 ≤ R ≤ 1), V (0 ≤ V ≤ 9)가 주어진다. C와 R은 격자에서 칸의 열과 행을 나타내고, V는 그 칸에 미리 정해진 값이다. 격자의 각 칸 값은 많아야 한 번 주어진다.

잡지 독자가 받을 수 있는 식스팩의 최대 개수를 출력한다. 이 수를 1 000 000 007로 나눈 나머지를 출력하시오.