407625: GYM102861 D Divisibility Dance

In the country of Nlogonia, the citizens perform a special dance to worship the God of divisibility. The dance is performed by $$$N$$$ men and $$$N$$$ women arranged in two concentric circles. The men position themselves on the inner circle, and the women on the outer circle. Every women starts out in front of some man.

The dance consists of $$$K$$$ steps; the first step is taken by the men, the second by the women and so on. At the $$$i$$$-th step, the people whose turn it is rotate $$$P_i$$$ positions in the clockwise direction, while the people in the other circle stay put. In this way, each person changes partner to someone $$$P_i$$$ positions away. A step is valid if every person's partner is different before and after the step AND if no pair of people ever face each other at two different moments in the process.

As part of the ritual, the dance must finish by forming pairs whose sum of ages leave the same remainder when divided by the sacred number $$$M$$$. In other words, if the sum of the ages of one couple (at the end of the dance) leaves remainder $$$R$$$ when divided by $$$M$$$, then every couple has to have sum of ages leaving remainder $$$R$$$ when divided by $$$M$$$.

Given $$$N$$$, $$$M$$$, $$$K$$$ and all of the dancers' ages, figure out in how many ways the dance can be performed. Since the dancers' ages are measured in seconds, the values can be very large.

The first input line contains three integers $$$N$$$ $$$(3 \le N \le 10^6)$$$, $$$M$$$ $$$(1 \le M \le 10^9)$$$ and $$$K$$$ $$$(1 \le K \le 10^9)$$$, corresponding to the number of people in each circle, to the sacred number and to the number of dance steps, respectively.

The second input line contains $$$N$$$ space-separated integers $$$A_i$$$ $$$(1 \le A_i \le 10^9)$$$, the ages of the women.

The second input line contains $$$N$$$ space-separated integers $$$B_i$$$ $$$(1 \le B_i \le 10^9)$$$, the ages of the men.

Initially, the $$$i$$$-th man is aligned with the $$$i$$$-th woman. For each vector of ages, the first element is considered to be to the right of the last one.

The output consists of a single integer, the remainder obtained by dividing the number of distinct dances by $$$10^9 + 7$$$.

4 10 1
3 4 1 7
13 27 36 9

1

5 10 2
3 4 1 7 6
4 7 1 2 5

3

5 10 2
3 4 1 7 6
5 4 7 1 2

4

6 21 3
10 58 23 31 37 2
45 17 9 24 38 30

42