CF852B.Neural Network country

Due to the recent popularity of the Deep learning new countries are starting to look like Neural Networks. That is, the countries are being built deep with many layers, each layer possibly having many cities. They also have one entry, and one exit point.

There are exactly L layers, each having N cities. Let us look at the two adjacent layers _L_1 and _L_2. Each city from the layer _L_1 is connected to each city from the layer _L_2 with the traveling cost c__ij for , and each pair of adjacent layers has the same cost in between their cities as any other pair (they just stacked the same layers, as usual). Also, the traveling costs to each city from the layer _L_2 are same for all cities in the _L_1, that is c__ij is the same for , and fixed j.

Doctor G. needs to speed up his computations for this country so he asks you to find the number of paths he can take from entry to exit point such that his traveling cost is divisible by given number M.

由于深度学习的近期流行，新兴国家开始呈现出神经网络的形态。也就是说，这些国家被构建成具有多层结构，每层可能包含多个城市。每个国家都有一个入口点和一个出口点。

恰好有 $L$ 层，每层恰好有 $N$ 个城市。考虑两个相邻层 $L_1$ 和 $L_2$。$L_1$ 层中的每个城市都与 $L_2$ 层中的每个城市相连，其通行代价为 $c_{ij}$（其中 $i=1,2,\dots,N$，$j=1,2,\dots,N$），即 ，且任意一对相邻层之间的城市通行代价矩阵均相同（正如通常做法那样，只是将相同的层堆叠起来）。此外，从 $L_1$ 层中任一城市前往 $L_2$ 层中某一特定城市 $j$ 的通行代价均相同，即对固定的 $j$，$c_{ij}$ 对所有 $i=1,2,\dots,N$ 都相等，亦即 。

G 医生需要加速对该国路径的计算，因此他请你求出从入口点到出口点的所有路径中，通行总代价能被给定整数 $M$ 整除的路径数目。

The first line of input contains N (1 ≤ N ≤ 106), L (2 ≤ L ≤ 105) and M (2 ≤ M ≤ 100), the number of cities in each layer, the number of layers and the number that travelling cost should be divisible by, respectively.

Second, third and fourth line contain N integers each denoting costs 0 ≤ cost ≤ M from entry point to the first layer, costs between adjacent layers as described above, and costs from the last layer to the exit point.

输入的第一行包含三个整数：$N$（$1 \leq N \leq 10^6$）、$L$（$2 \leq L \leq 10^5$）和 $M$（$2 \leq M \leq 100$），分别表示每层的城市数量、层数，以及旅行总花费必须能被整除的数。

第二、第三和第四行各包含 $N$ 个整数，分别表示：从入口点到第一层各城市的花费（$0 \leq \text{cost} \leq M$）、如上所述的相邻层之间的花费，以及从最后一层各城市到出口点的花费。

Output a single integer, the number of paths Doctor G. can take which have total cost divisible by M, modulo 109 + 7.

输出一个整数，表示医生 G. 可以选择的、总代价能被 $M$ 整除的路径数量，结果对 $10^9 + 7$ 取模。

This is a country with 3 layers, each layer having 2 cities. Paths , and are the only paths having total cost divisible by 13. Notice that input edges for layer cities have the same cost, and that they are same for all layers.

这是一个拥有 3 层的国家，每层包含 2 座城市。路径 和 是仅有的总代价能被 13 整除的路径。注意：连接各层城市与输入端点的边具有相同的代价，且该代价在所有层中均相同。