14679번 - 영우와 ‘갓4’

게임을 좋아하는 영우는 오늘도 ‘갓4’ 라는 게임을 한다. ‘갓4’의 게임 시스템은 신기한데 우선 캐릭터와 몬스터는 각각 공격력(A), 방어력(D), 최대 체력(H)이 주어진다. ‘갓4’의 전투 시스템은 1:1 전투이며 다음과 같다.

1. 자기의 턴이 오면 상대방을 공격할 수 있으며, [(자신의 공격력 – 상대방의 방어력), 1] 중에 더 높은값만큼 상대방의 체력을 깎는다.
2. 공격이 끝나면 상대 턴으로 넘어간다.
3. 어느 한쪽의 체력이 0 이하로 떨어질 때까지 계속하며, 먼저 체력이 0 이하로 떨어진 쪽이 진다.
4. 모든 전투는 영우의 캐릭터가 먼저 공격한다.

또한 몬스터와의 전투에서 승리하면 캐릭터는 몬스터의 능력치를 그대로 흡수한다. 즉 (5, 5, 5)의 능력치를 가진 캐릭터가 (1, 1, 1)의 능력치를 가진 몬스터와 싸워 승리하면 캐릭터는 (6, 6, 6)의 능력치를 가지게 되는 것이다. 또한 몬스터와의 전투에서 승리하면 캐릭터는 다시 체력을 최대치까지 회복한다. 영우는 총 N마리의 몬스터를 연속해서 지지않고 잡고 싶다. 즉 모든 몬스터와의 전투에서 이겨야 한다는 뜻이다. N마리 몬스터의 데이터를 모두 입력으로 주기에는 데이터의 크기가 너무 커지므로 다음과 같이 수식으로 대체하도록 했다.

k번째(k > 1) 몬스터의 공격력(A_k), 방어력(D_k), 최대 체력(H_k)는 다음과 같다.

• A_k = ((A_k-1^A_p + A_a) % 100) + 1
• D_k = ((D_k-1^D_p + D_a) % 3) + 1
• H_k = ((H_k-1^H_p + H_a) % 1000) + 1

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 몬스터의 수 N이 주어진다. (1 ≤ N ≤ 50,000,000) 두 번째 줄에는 영우가 키우는 캐릭터의 공격력(A), 방어력(D), 최대 체력(H)이 차례대로 주어진다. (1 ≤ A ≤ 100) (1 ≤ D ≤ 3) (1 ≤ H ≤ 1000) 세 번째 줄에는 첫 번째 몬스터의 공격력(MA), 방어력(MD), 최대 체력(MH)이 차례대로 주어진다. (1 ≤ MA ≤ 100) (1 ≤ MD ≤ 3) (1 ≤ MH ≤ 1000) 넷째 줄에 몬스터의 능력치를 구하는데 사용되는 값(A_p, A_a, D_p, D_a, H_p, H_a)이 차례대로 주어진다. (1 ≤ A_p, D_p, H_p ≤ 1,000,000,000) (0 ≤ A_a ≤ 99) (0 ≤ D_a ≤ 2) (0 ≤ H_a ≤ 999) 

프로그램의 출력은 표준 출력으로 한다. 영우가 N마리의 몬스터를 잡았을 때 갖는 최종 능력치를 1,000,000,007로 나눈 나머지를 공격력(A), 방어력(D), 최대 체력(H) 순으로 공백으로 구분하여 출력한다. 만약영우가 N마리의 몬스터를 연속해서 잡을 수 없다면 -1을 출력한다.