Informatica Online Judge

  스킬 트리 [2162 / 0872]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 4


The Champion of this Problem (C++) : gs17068 - 136ms / 1237byte
My Best Submission (C++) : N/A

[koistudy.net(33rd 김동현)]

Background

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

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

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

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

Input

첫 번째 줄에는 A와 B가 주어진다. (각각 1 이상 109 이하)

두 번째 줄에는 특별한 삼각형의 개수 N (1≤N≤100000) 이 주어진다.

다음 N개의 줄에는 각 특별한 삼각형을 나타내는 정수 xi, yi, mi 가 공백을 사이에 두고 주어진다. (모두 1 이상 1018 이하)

Output

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

IO Example

입력
2 3
3
1 1 2
2 2 3
4 3 2

출력
6
75
108

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]