## EXLAGFIB - Extremely Lagged Fibonacci

Let $(\ a_i\ )_{i=0}^\infty$ be the integer sequence such that: $$a_n = \begin{cases} 0 & (0 \le n < k - 1) \\ 1 & (n = k - 1)\\ b \cdot a_{n-j} + c \cdot a_{n-k} & (n \ge k) \end{cases},$$ where $j$, $k$, $b$ and $c$ is integer.

For each $n, j, k, b$ and $c$, find $a_n$ modulo $1\,000\,000\,037$.

### Input

The first line contains $T$, the number of test cases.

Each of the next $T$ lines contains five integers $n, j, k, b$ and $c$.

### Output

For each test case, print $a_n$ modulo $1\,000\,000\,037$.

### Constraints

• $1 \le T \le 10^2$
• $0 \le n \le 10^9$
• $10^5 \le k \le 10^8$, $1 \le j < k$
• $1 \le b \le 10^9$, $1 \le c \le 10^9$

### Example

Input:
2
1000000 1 100000 1 1
1000000000 1 100000000 1 1

Output:
372786243
994974348


hide comments Min_25: 2016-09-22 13:27:38 @:D Thank you ! My best (total) time is around 0.24 sec. :D: 2016-09-22 02:16:20 Great problem. Seems like another variant on fib / recursive sequences, but it's actually really original. Finding efficient solution was very interesting. Thanks for setting it up min_25! P.S. For reference, what's your best time on this problem? Last edit: 2016-09-22 02:17:17 Min_25: 2016-04-26 19:29:46 @Blue.Mary Thanks, 1KB limit was tough for me ... :) Last edit: 2016-04-26 19:29:55 [Rampage] Blue.Mary: 2016-04-25 06:25:31 A 1024 byte source limit may make this problem more interesting :-)

 Added by: Min_25 Date: 2016-04-25 Time limit: 5s-8s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 GOSU JS-MONKEY