You have to find the n^th term of the following function:

$$f(n) = \begin{cases} a \times f(n-1) + b \times f(n-3) + c, & \text{if $n$ > 2} \cr 0, & \text{if $n$ ≤ 2} \end{cases}$$

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

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

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