비료 주기

경근이는 세계에서 제일가는 콩나무 농부가 되는 것이 꿈이다. 오늘도 꿈을 좇아 애쓰던 경근이는 식물에 뿌리기만 하면 쑥쑥 자라게 하는 비료 X를 마침내 개발했다. 다만 비료 X의 효과가 워낙 강해서 한 번에 제어할 자신이 없었던 경근이는 비료의 강도를 조금씩 높여 가며 콩나무 기르기에 익숙해지기로 했다.

경근이에게는 콩나무 씨앗 N개가 있다. 씨앗을 막 땅에 심었으므로 모든 나무의 높이는 0이다. 경근이는 앞으로 D일 동안 하루에 한 번씩 콩나무에 비료를 준다.

i번째 날(1 ≤ i ≤ D)에 비료를 흡수한 나무는 높이가 i만큼 자란다. 이날 비료를 받는 나무는 현재 높이가 가장 낮은 $C_i$개다. 높이가 같은 나무가 여럿이면 그중 무엇을 골라도 결과는 같다.

비료를 준 직후 경근이는 나무가 얼마나 잘 자랐는지 확인하려고 $K_i$번째로 작은 나무의 높이를 기록한다.

꿈이 너무 컸던 경근이는 감당할 수 없는 수의 콩나무를 심고 말았다. 경근이를 도와 D일 동안 기록한 높이의 합을 구하라.

첫째 줄에 테스트 케이스의 수를 뜻하는 자연수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄에 정수 다섯 개 N, D, s, a, b로 주어지며, 값은 공백으로 구분된다 (1 ≤ N, D ≤ 100,000, 0 ≤ s, a, b ≤ 100,000).

$C_i$와 $K_i$는 s, a, b로 다음과 같이 생성한다. 중간 계산은 64비트 정수로 한다.

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일 동안 기록한 나무 높이의 합을 한 줄에 출력한다. 이 합은 32비트 정수 범위를 넘을 수 있다.