29815번 - 발전 장치

문제

대학 졸업 직후 취업에 바로 성공한 김한양은 이제 LG전자 연구실에서 새로운 발전 장치를 개발하고 있다.

이 발전 장치는 아래의 [그림]과 같이 가로와 세로의 길이가 각각 1ドル$인 모듈들이 피라미드 모양으로 연결된 구조이다. 발전 장치는 총 $N$층 높이로, 지면에 가장 가까운 1ドル$층부터 가장 먼 $N$층까지 있다. 1ドル$층에는 $N$개, 2ドル$층에는 $N - 1$개, $\dots,ドル $N$층에 1ドル$개의 모듈이 일렬로 나열되어 있다. 발전 장치의 $R$층의 $C$번째 칸에 있는 모듈을 $(R, C)$로 표현한다.

[그림]

각 층의 가장 왼쪽과 가장 오른쪽에 위치하는 모듈은 태양광을 이용하여 전기를 만드는 생산 모듈이다. 이때, $N$층에는 생산 모듈 하나만 가운데에 있다. 생산 모듈은 태양과의 높이차에 영향을 받기 때문에 가로의 위치와 관계없이 세로인 층수가 높아질수록 전기를 더 많이 생성한다. 1ドル$층에 있는 생산 모듈의 충전 속력을 $A,ドル 생산 모듈의 높이가 1ドル$씩 올라갈 때마다 증가하는 충전 속력의 변화량을 $B$라 하면, 층수에 따른 생산 모듈의 충전 속력은 첫째항이 $A$이고 공차가 양수 $B$인 등차수열을 이룬다.

그 외의 모듈은 모두 합산 모듈로, 위층의 양옆에 있는 두 모듈의 전기량을 그대로 합산하여 가져온다. 즉, $(R,\ C)$에 있는 합산 모듈의 충전 속력은 각각 $(R + 1,\ C - 1)$과 $(R + 1,\ C)$에 위치하는 두 모듈의 충전 속력의 합과 같다.

김한양은 이 발전 장치가 제대로 작동하는지 확인하기 위해 각 모듈의 충전 속력을 계산해 주는 프로그램이 필요하다. 발전 장치에 대해 주어진 정보를 바탕으로 이 프로그램을 한번 만들어 보자!

입력

첫 번째 줄에는 세 양의 정수 $A,ドル $B,ドル $N$이 공백을 사이로 주어진다. $(1 ≤ A,\ B ≤ 10^9;\ 1 ≤ N ≤ 2 \times 10^6)$

두 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. $(1 ≤ T ≤ 2 \times 10^5)$

이어서 $T$개의 줄에 걸쳐서 두 양의 정수 $R,ドル $C$가 공백을 사이로 주어진다. $(1 ≤ R,\ C ≤ N;\ R + C ≤ N + 1)$

출력

각 테스트 케이스마다 $(R, C)$에 위치한 모듈의 충전 속력을 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

노트