FINDLR  Find Linear Recurrence
You are given the first $2K$ integers $a_0, a_1, \ldots, a_{2K1}$ (modulo $M$) of an infinite integer sequence $(a_i)_{i=0}^{\infty}$ that satisfies an integercoefficient linear recurrence relation of order $K$.
That is, they satisfy $$ a_n = \sum_{i=1}^{K} c_i a_{ni} $$ for $n \ge K$, where $c_1, \ldots, c_K$ are integer constants.
Find $a_{2K}$ modulo $M$.
Input
The first line contains $T$ ($1 \le T \le 4000$), the number of test cases.
Each test case consists of two lines:
 First line contains $K$ ($1 \le K \le 50$) and $M$ ($1 \le M < 2^{31}$).
 Next line contains $2K$ integers $a_0, a_1, \ldots, a_{2K1}$ (modulo $M$).
Note: $M$ is not necessarily a prime.
Output
For each test case, output $a_{2K}$ modulo $M$.
Example
Input
6 1 16 4 8 1 10 4 8 2 64 13 21 34 55 2 27 13 21 7 1 3 1000000007 32 16 8 4 2 1 2 64 13 21 34 56
Output
0 6 25 8 500000004 40
hide comments
userhacker_1:
20180314 07:45:42
@min_25 > it was better you give tutorial for your problems(all) or give some article about knowledge of solving your problems! Last edit: 20180315 10:36:25 

Min_25:
20180101 05:22:03
@zimpha: Thank you! 

zimpha:
20171231 16:28:25
@Min_25 Very nice problem! 

Min_25:
20171216 12:38:14
@Scape: Each c_i is an integer. So, there are no such cases. 

Scape:
20171216 12:28:39
If M is not a prime, sometimes there might be no solution.


Min_25:
20171021 02:39:05
@Blue.Mary


[Rampage] Blue.Mary:
20171021 02:15:04
I'm not sure if this problem coincide with this one:

Added by:  Min_25 
Date:  20171020 
Time limit:  5s15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 