FINDLR - Find Linear Recurrence

You are given the first $2K$ integers $a_0, a_1, \ldots, a_{2K-1}$ (modulo $M$) of an infinite integer sequence $(a_i)_{i=0}^{\infty}$ that satisfies an integer-coefficient linear recurrence relation of order $K$.

That is, they satisfy $$ a_n = \sum_{i=1}^{K} c_i a_{n-i} $$ 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_{2K-1}$ (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

Added by:Min_25
Date:2017-10-20
Time limit:5s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-03-14 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: 2018-03-15 10:36:25
2018-01-01 05:22:03 Min_25
@zimpha: Thank you!
2017-12-31 16:28:25 zimpha
@Min_25 Very nice problem!
2017-12-16 12:38:14 Min_25
@Scape: Each c_i is an integer. So, there are no such cases.
2017-12-16 12:28:39 Scape
If M is not a prime, sometimes there might be no solution.

For example, what should be the output for the fifth case if M is 4?

3 4
32 16 8 4 2 1

Can you please check and clarify?
2017-10-21 02:39:05 Min_25
@Blue.Mary
Thank you. I did not know that problem.
I think DYEL is a little easier than this because (a_i) are given in Z.

However, some solutions in DYEL might be used for this problem with little modification.

Last edit: 2017-10-21 03:08:22
2017-10-21 02:15:04 [Rampage] Blue.Mary
I'm not sure if this problem coincide with this one:
http://www.spoj.com/problems/DYEL/

Cound the author have a look at this?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.