Server Time: Thu Apr 26, 2018 5:31 am
Welcome ( logout
1096 - nth Term
  PDF (English) Statistics Forum
Time Limit: 1 second(s) Memory Limit: 32 MB

You have to find the nth term of the following function:

f(n)      = a * f(n-1) + b * f(n-3) + c, if(n > 2)

= 0, if(n ≤ 2)

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output

For each case, print the case number and f(n) modulo 10007.

Sample Input

Output for Sample Input

2

10 1 2 3

5 1 3 9

Case 1: 162

Case 2: 27

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan