시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 88 25 20 26.667%

문제

혁중이는 요즘 리X 오브 레X드에 빠져 메X플스X리를 소홀히 했다. 그러던 어느 날, 보스를 잡던 손맛이 그리워진 혁중이는 메X플스X리에 다시 접속했는데, 아니 이게 무슨 일인가! 자신이 모르던 사이에 이미 6차 전직이 업데이트 된 것이다.

6차 전직의 스킬트리는 무한히 큰 정삼각형 모양 격자 형태로, 가장 위 꼭지점에 위치한 스킬을 배우는 데 $1$원이 들고, 임의의 칸의 스킬을 배우는 비용이 $k$원이라면 왼쪽 아래 칸은 $Ak$원, 오른쪽 아래 칸은 $Bk$원이 든다.

스킬트리에는 $N$개의 특별한 삼각형이 정해져 있다. 각 특별한 삼각형은 $x_i$, $y_i$, $m_i$의 세 가지 수로 나타내지며, 격자의 $x_i$번째 행의 왼쪽에서 $y_i$번째 칸을 위쪽 꼭짓점으로 하고, $m_i$개의 행을 포함하는 정삼각형을 의미한다. 각 특별한 삼각형 내의 스킬을 모두 배울 때마다 총 데미지가 2배씩 증가한다고 한다!

혁중이는 각 특별한 삼각형에 대해 그 안에 있는 스킬을 모두 배우는 데 얼마의 비용이 드는지 궁금해졌다. 혁중이를 도와주자!

입력

첫 번째 줄에는 $A$와 $B$가 주어진다. (각각 $1$ 이상 $10^{9}$ 이하)

두 번째 줄에는 특별한 삼각형의 개수 $N$ ($1 \le N \le 100\, 000$) 이 주어진다.

다음 $N$개의 줄에는 각 특별한 삼각형을 나타내는 정수 $x_i$, $y_i$, $m_i$ 가 공백을 사이에 두고 주어진다. (모두 $1$ 이상 $10^{18}$ 이하)

출력

각 특별한 삼각형에 대해, 그 안에 있는 스킬을 모두 배우는 데 드는 비용을 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

2 3
3
1 1 2
2 2 3
4 3 2

예제 출력 1

6
75
108

힌트