경근이는 세계에서 제일가는 콩나무 농부가 꿈이다. 오늘도 꿈을 이루기 위해서 고군분투 하던 경근이는 마침내 식물에게 뿌리기만 하면 식물이 쑥쑥 자라게 하는 비료X를 개발하는데 성공했다. 다만 비료X의 너무나도 강력한 효과를 잘 제어할 자신이 없었던 경근이는 비료X의 강도를 서서히 높여가면서 콩나무 기르기에 익숙해지고자 마음먹었다.</p>

경근이는 현재 N개의 콩나무 씨앗을 가지고 있으며, 이제 막 씨앗들을 땅에 심었기 때문에 높이가 0이다. 경근이는 앞으로 D일에 걸쳐 하루에 한 번씩 콩나무들에게 비료를 주고자 한다.

i (1 ≤ i ≤ D)번째 날에는 비료를 흡수하면 높이가 i만큼 자라도록 비료X를 주려고 하는데, 이때 비료를 주는 대상은 현재 높이가 가장 낮은 C_i개의 나무이다.

또한 경근이는 비료가 콩나무들이 얼마나 잘 자라는지 알고 싶기 때문에 매일매일 비료를 주고 나서 현재 K_i번째로 작은 나무의 높이가 무엇인지를 알고 싶다.

하지만 꿈이 너무 컸던 경근이는 감당할 수 없는 수의 콩나무를 심어버리고 말았다. 당신은 경근이를 도와 비료를 주면서 콩나무를 관찰하는 일을 해야한다.

입력 형식

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.</p>

각 테스트 케이스는 5개의 정수로 나타내어지며, 이를 나타내는 N, D (1 ≤ N, D ≤ 100,000), s, a, b (0 ≤ s, a, b ≤ 100,000) 가 공백으로 구분되어 주어진다.

C_i와 K_i는 s, a, b를 이용해서 생성할 수 있으며 그 방법은 아래와 같다.

for (int i=1; i<=D; i++) {
    Ci = s % N + 1;
    s = (s  a + b) % 1000000007;
    Ki = s % N + 1;
    s = (s  a + b) % 1000000007;
}

각 테스트 케이스당 한 줄에 D일 동안 측정된 나무 높이들의 합을 출력한다.

예제 입력

3
5 5 4 4 4
5 5 3 3 3
5 5 2 2 2

예제 출력

35
30
22