시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 48 6 6 35.294%

문제

게임을 좋아하는 영우는 오늘도 ‘갓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) 몬스터의 공격력(Ak), 방어력(Dk), 최대 체력(Hk)는 다음과 같다.

  • Ak = ((Ak-1Ap + Aa) % 100) + 1
  • Dk = ((Dk-1Dp + Da) % 3) + 1
  • Hk = ((Hk-1Hp + Ha) % 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) 넷째줄에 몬스터의 능력치를 구하는데 사용되는 값(Ap, Aa, Dp, Da, Hp, Ha)이 차례대로 주어진다. (1 ≤ Ap, Dp, Hp ≤ 1,000,000,000) (0 ≤ Aa ≤ 99) (0 ≤ Da ≤ 2) (0 ≤ Ha ≤ 999) 

출력

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

예제 입력

3
11 1 15
11 1 20
1 10 1 0 1 10

예제 출력

77 7 108

예제 입력 2

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

예제 출력 2

-1

힌트