EXLAGFIB - Extremely Lagged Fibonacci

Let ( ai )i=0(\ a_i\ )_{i=0}^\infty be the integer sequence such that: an={0(0n<k1)1(n=k1)banj+cank(nk),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 jj, kk, bb and cc are integers.

For each n,j,k,bn, j, k, b and cc, find ana_n modulo 10000000371\,000\,000\,037.

Input

The first line contains TT, the number of test cases.

Each of the next TT lines contains five integers n,j,k,bn, j, k, b and cc.

Output

For each test case, print ana_n modulo 10000000371\,000\,000\,037.

Constraints

  • 1T1021 \le T \le 10^2
  • 0n1090 \le n \le 10^9
  • 105k10810^5 \le k \le 10^8, 1j<k1 \le j < k
  • 1b1091 \le b \le 10^9, 1c1091 \le c \le 10^9

Example

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

Output:
372786243
994974348

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

hide comments
2016-09-22 13:27:38 Min_25
@:D
Thank you ! My best (total) time is around 0.24 sec.
2016-09-22 02:16:20 :D
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
2016-04-26 19:29:46 Min_25
@Blue.Mary
Thanks, 1KB limit was tough for me ... :)

Last edit: 2016-04-26 19:29:55
2016-04-25 06:25:31 [Rampage] Blue.Mary
A 1024 byte source limit may make this problem more interesting :-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.