문제 설명
청주 문의면 일대에서 열리는 영춘제를 위해 직사각형 모양의 땅에 삼각형 모양으로 꽃밭을 만들고자 한다. 땅에는 구간을 나누기 위해 일정한 간격으로 말뚝이 심어져 있고, 각 말뚝 위치는 좌표로 표현한다. 꽃밭은 말뚝 세 개를 일직선으로 이어서 만든다. 단, 말뚝과 말뚝을 이을 때는 중간에 다른 말뚝이 있으면 꽃밭을 만들 수 없다.
예를 들어, [예시1]과 같은 경우에는 (1, 1), (2, 1), (2, 2)를 이어서 꽃밭을 만들 수 있다.
[예시2]와 같은 경우에는 (1, 1)과 (1, 3)을 잇는 중간에 (1, 2)에 말뚝이 있기 때문에 꽃밭을 만들 수 없다.
땅의 크기인 N, M과 입력받을 말뚝의 개수(T), 이후 T개의 줄에 말뚝의 좌표(x, y)가 주어지면, 각 말뚝에서 만들 수 있는 삼각형 모양의 땅의 경우의 수를 10,007로 나눈 나머지를 T개의 줄에 걸쳐 출력하는 프로그램을 작성해보자.
입력 설명
첫 번째 줄에 땅의 크기를 나타내는 행(N), 열(M)이 공백으로 구분되어 입력된다.
(단, N ,M은 정수이고, 2 ≤ N, M ≤ 40 의 범위를 갖는다.)
두 번째 줄에 입력받을 점들 말뚝의 개수(T)가 입력된다.
(단, T는 정수이고, 1 ≤ T ≤ 50 의 범위를 갖는다.)
세 번째 줄부터 이후 T개의 줄에 말뚝의 좌표(x, y)가 입력된다.
(단, x, y는 정수이고, 1 x ≤ N, 1 ≤ y ≤ M 의 범위를 갖는다.)
출력 설명
말뚝(x, y)에서 만들 수 있는 꽃밭의 수를 10,007로 나눈 나머지를 T줄에 걸쳐 출력한다.