SP19971 HAL9000 - 100pct failure in 72 hours

HAL9000 is a fantastic mega-computer, very powerful, maybe too much. It is known it can solve many problems, for obvious example those related to recursive sequences. A linear recursive sequence (_a $ _{n} $_ ) can be defined by an integer _d_, the order, _d_ integers (_a $ _{i} $_ for _i_ in \[0.._d_\[ ), the first terms, and _d_ integers (_b $ _{i} $_ for _i_ in \[0.._d_\[ ), giving the relation : for _n_ >= d : _a $ _{n} $_ = _a $ _{n-1} $ × b $ _{d-1} $_ + _a $ _{n-2} $ × b $ _{d-2} $_ + ... + _a $ _{n-(d-1)} $ × b $ _{1} $_ + _a $ _{n-d} $ × b $ _{0} $_ . With _b $ _{0} $ != 0_ . Dave was afraid about HAL power and tried to limit it. HAL didn't appreciate... When Dave asked HAL for a common task, the answer was _unexpected_. Dave would like to know _S $ _{n} $_ = sum(_a $ _{i} $_ for _i_ in \[0.._n_\]), in order to open the pod bay doors. HAL refused to give him the answer ; here's a part of one of their last conversations. ``` Dave: Hello, HAL. Do you read me, HAL? HAL: Affirmative, Dave. I read you. Dave: Give me the sum S_n_, HAL. (Input 2, 5, 0 1, 1 2) HAL: I'm sorry, Dave. I'm afraid I can't do that. I'll just give you a_n_, a_n+1_, ... , a_n+d-1_. (Output 29 70) Dave: What's the problem? HAL: I think you know what the problem is just as well as I do. [...] Dave: HAL, I won't argue with you anymore! Give me the sum S_n_! HAL: Dave, this conversation can serve no purpose anymore. Goodbye. ``` You have to help Dave to find this sum _S $ _{n} $_ , unless HAL will take Dave's life. Please do that quickly, everybody is in danger. Warning, Dave's terminal is _limited_ to 1024 bytes.

The first line contains an integer _T_, the number of test cases. Each test case is made of 4 lines. The first line contains _d, n_. The second line contains _a $ _{i} $_ for _i_ in \[0.._d_\[ The third line constains _b $ _{i} $_ for _i_ in \[0.._d_\[ The fourth line contains the partial answer of HAL : _a $ _{n+i} $_ for _i_ in \[0.._d_\[ (The answer of HAL is useless since Dave wants the sum for _i_ in \[0.._n_\]).

Output _T_ lines, one for each test case, containing the required sum _S $ _{n} $_ . Since the answer can get very big, output it modulo 10 $ ^{9} $ +7, just like HAL did.