eolymp
bolt
Try our new interface for solving problems
Problems

A night in the Library

A night in the Library

Time limit 1 second
Memory limit 64 MiB

One summer Jack had "working practice" in the school library: he was fixing old textbooks, helping the librarians with sorting books, etc. Jack always sticks his snout into everything, and math textbooks were no exception.

In one of the books he saw the following:

… denoted using D(M) — a skew-symmetric polylinear normed function of square matrix columns, i.e.:

1. If two columns of the matrix are swapped, its value changes sign:

2. If a matrix column is a linear combination of two vectors, the linear combination can be taken out:

3. On the identity matrix it equals 1:

Let us prove that such a function is unique:

… (Jack skips pages and reads in small bits) …

… for example using Gaussian elimination.

… (very small bits) …

… the matrix X is the product of the column u and the row v, i.e.:

Jack is very intrigued by what he’s just read. Jack enjoys competitive programming and spends all his time on the Codeforces website, so he’s not at all afraid of matrices and vectors. But his math could use some improvement.

Jack wants to calculate the value of the mentioned skew-symmetric polylinear normed function D for the matrix X defined in the last bit of text. To make things easier all elements of the vectors u and v are integers. He has a hunch that the answer is an integer too. Since he has a feeling that it can be very, very big, Jack wants to find it modulo prime number P ((that’s how things are usually done).

Help Jack solve the task. Otherwise the aforementioned website will be spammed.

Input data

The first line contains two integers N and P (1N100, 2P2·10^9). It is guaranteed that P — is a prime number. The second line contains N integers u_1, u_2, …, u_n — elements of the column vector u, and the third line contains N integers v_1, v_2, …, v_n — elements of the row vector v (0u_i, v_j < P).

Output data

The output file must contain a single integer: the value of D(X) modulo P. The number must be non-negative and strictly less than P.

Examples

Input example #1
3 11
0 7 8
10 5 3
Output example #1
0
Source XIII All-Siberian Programming Contest named after I.V.Pottosin, November 11, 2012