Dibs on Fibs
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.You are given two sequences $A$ and $B$, each with size $M$, and an integer $N$. Consider the following pseudocode: ``` result := 0 for i := 1 to M for j := 1 to M array fib[1..max(2, N)] fib := A[i] fib := B[j] for k := 3 to N fib[k] := fib[k-1] + fib[k-2] result := result + fib[N] ``` Compute the final value of the variable `result`. Since it can be very large, compute its remainder modulo $10^9+7$. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-seperated integers $M$ and $N$. - The second line contains $M$ space-seperated integers $A_1, A_2, \dots, A_M$. - The third line contains $M$ space-seperated integers $B_1, B_2, \dots, B_M$. ### Output For each test case, print the final value of `result` modulo $10^9+7$. ### Constraints - $1 \le T \le 10$ - $1 \le M \le 10^5$ - $1 \le N \le 10^5$ - $0 \le A_i, B_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (20 points):** $1 \le N, M \le 100$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 1 3 3 1 2 3 4 5 6 ``` ### Example Output ``` 63 ``` ### Explanation **Example case 1:** The innermost loop is ran for 9 pairs of initial values: $(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)$. The corresponding values added to `result` are $5, 6, 7, 6, 7, 8, 7, 8, 9$, and their sum is 63.
|Tags||anuj_2106, easy, fibonacci-numbers, may18|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.