와 같은 꼴로 수열의 점화식이 주어진다. a_n 을 k 로 나눈 나머지를 구하면 된다. a_n 은 n 번째 항 , a_n-1 은 (n-1) 번째 항을 나타낸다.

입력

• 첫 줄의 질문의 수 Q( 1 <= Q <= 32767) 가 입력으로 들어온다.
• 다음 Q 줄에 5 개의 자연수 a_1 , p , q , k , n 이 주어진다. a_1 , p,q,k,n 은 10⁹ +9 이하이다. a_1 은 첫 번째 항의 값을 나타낸다.

출력

입출력 예

입력

4
1 3 2 100 4
1 2 1 2 5
1 2 1 1000000 20
2 3 4 32767 5

출력

53
1
48575
322

입출력 보충

• a_1 = 1 ,
• a_2 = 3a_1 + 2 = 5 ,
• a_3 = 17 ,
• a_4 = 53

출처:sharifa