J19 实践-5 神经网络国家

题目描述

由于深度学习最近的流行，新的国家开始看起来像神经网络。也就是说，这些国家正在被建造成多层，每一层都可能有许多城市。它们还有一个入口和一个出口。

正好有 $L$ 层，每层都有 $N$ 个城市。让我们看看两个相邻的层 $L_1$ 和 $L_2$。来自层 $L_1$ 的每一个城市都与来自层 $L_2$ 的每座城市相连，并且每一对相邻的层在其城市之间的旅行成本 $c_{ij}$ 与任何其他层相同（它们通常只是堆叠了相同的层）。此外，对于 $L_1$ 中的所有城市，从层 $L_2$ 到每个城市的旅行成本是相同的，即 $c_{ij}$ 对于 $j$ 是相同的并且是固定的。

G博士需要加快对这个国家的计算速度，所以他要求你找出他从入口到出口可以走的路径数，路径上的旅行成本符合可以被给定的 $M$ 整除。

输入格式

第一行输入包含 $N$，$L$ 和 $M$，分别每层中的城市数量、层的数量和旅行成本应分别除以的数量。

第二、第三和第四行包含 $N$ 个整数，每个整数表示成本 $0\le c_{ij}\le M$ , 从入口点到第一层，如上所述相邻层之间的成本，以及从最后一层到出口点的成本。

输出格式

输出一个整数，G博士可以采取的路径数，其总成本可除以 $M$，模 $10^9+7$.

样例输入

2 3 13
4 6
2 1
3 4

样例输出

2

样例分析

这是一个有三层的国家，每层有两个城市。路径$6 \to 2 \to 2 \to 3$、和 $6 \to 2 \to 1 \to 4$ 是总成本可被 $13$ 整除的唯一路径。请注意，层城市的输入边具有相同的成本，并且所有层的输入边都相同。

数据范围

对于 $100\%$ 的数据：$1 \le N\le 10^6$, $2\le L\le 10^5$ , $2\le M\le 100$。