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$ are integers.
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
|
|
: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!
|
|
Min_25:
2016-04-26 19:29:46
@Blue.Mary
|
|
[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 |