보물

그래서 내가 이 꼴이 됐지, 짐. 다 젊었을 때 공동묘지에 가서 동전 던지기를 했기 때문이야!

벤 건

섬에 혼자 남은 벤 건은 정신이 나갔다. 그는 동굴 속 보물을 $n$개의 더미로 나누어 한 줄로 늘어놓았다. 지금 그에게는 플린트 선장의 환영이 보이고, 그 환영은 보물의 일부를 빼앗으려 한다.

플린트는 환영일 뿐이므로 요구하는 방식이 특이하다. 그는 줄에서 연이어 놓인 $k$개의 더미를 골라, 그 더미들의 가치 합이 나머지 모든 보물의 가치 합 이상이 되기를 원한다. 이때 고르는 더미의 개수는 가능한 한 적어야 한다.

벤 건은 각 더미의 가치를 정확히 말하지 못한다. 기억하는 것은 처음 두 더미의 가치와, $i$번째 더미의 가치를 다음 식으로 계산했다는 사실뿐이다.

$(a \cdot t_{i-2} + b \cdot t_{i-1} + c) \mod d$

여기서 $a$, $b$, $c$, $d$는 닉 올라르다이스가 알려준 상수이고, $t_{i-1}$과 $t_{i-2}$는 각각 $i-1$번째와 $i-2$번째 더미의 가치이다.

벤 건이 플린트에게 보물의 일부를 넘겨주도록 도와라.

첫 줄에 더미의 개수 $n$ ($2 \le n \le 10^7$)이 주어진다. 둘째 줄에는 처음 두 더미의 가치 $x$와 $y$ ($0 \le x,y \le 10^9$)가 주어진다. 셋째 줄에는 $a$, $b$, $c$, $d$ ($0 \le a, b, c \le 10^9, 1 \le d \le 10^9$)가 주어진다.

플린트가 가져갈 첫 번째 더미와 마지막 더미의 번호를 출력한다. 답이 여러 개이면 그중 아무거나 출력해도 된다.

이 문제는 메모리가 적으니 주의하라.