{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRather than drinking happy water, Guanguan loves storing happy water. So he bought a refrigerator and stored $a_i$ bottles of cola into it every day. When the storage is finished on the $k$-th day, the refrigerator is full, but he still wants to store happy water every day. Here comes the solution: He first constructs a p-sequence: $p_1$, $p_2$, ..., $p_k$, where $p_1+p_2+...+p_k\u003d1$. Then he chooses an number $i$ among $1$ to $k$, where number $i$ has the probability $p_i$ to be chosen. After that, he drinks the happy water stored on the $i$-th day before the current day and stores the same amount of happy water back into the refrigerator again. Let the amount of happy water stored on the $i$-th day be $f_i$. Given the amount of happy water stored in the first $k$ days and the expected amount of the next $k$ days(which means, from the $k+1$-th day to the $2k$-th day), could you help Guanguan figure out the sum of the expected amount of happy water stored during the first $n$ days) (Be aware that every element of $f$ has moded $1e9+7$ when input datas, and your output should mod $1e9+7$ as well)\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe first line is $T$ ($1 \\le T \\le 20$), indicating the number of input sets. For each set of inputs, the first line is $k$ and $n$ ($1 \\le k \\le 70$, $1 \\le n \\le 10^{18}$), and the second line is $2k$ numbers, respectively representing $a_1$, $a_2$, ..., $a_k$, $f_{k+1}$, $f_{k+2}$, ..., $f_{2k}$.\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eFor each data, output a non-negative integer indicating $(\\sum_{i\u003d1}^n f_i) \\mod 10^9+7$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 9\n2 2\n2 8\n6 5 5 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\n41\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}