NIO would like to be an electrician.

He is now confronted with a difficult task. The device he is working on has a circular frame and there are equidistant vertices on the frame. It can be simplified to a circle on a two-dimensional plane. In addition to the outermost circular frame, there are also vertices on the frame. It can be simplified to a circle on a two-dimensional plane. In addition to the outermost circular frame, there are also holders inside which can be simplified to segments connecting the vertices on the circle. Because these holders are produced together, they are all the same "length" . "Length" means that if a segment start at -th vertex, it would end at -th vertex and must satisfy .

The task is to place two wires on the frame, one from vertex to and another from to . The wires must be close to the segments or arcs on the frame and on where two segments intersect, a wire can also be connected from one segment to another. For safety, two wires cannot intersect at any position, that is, they can not pass through the same vertex or intersections of segments, including vertex 1, 2, For safety, two wires cannot intersect at any position, that is, they can not pass through the same vertex or intersections of segments, including vertices 1, 2, and . And on any segment and arc, the wire must follow the direction from the vertex with the small number to the vertex with the large number.

NIO wants to know how many schemes he has for placing wires.

Since the answer is too large, NIO only wants to know it modulo ..

The first line contains two integers , ,  .

The following line contains  distinct integers  , donating that there is a segment connecting  and .

A single non-negative integer, denoting the answer, modulo .

6 3 1
1 2 3

4

12 5 4
1 2 5 7 8

42