SP26916 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 $ .

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 $ .

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