CF852B Neural Network country

由于最近深度学习的流行，新的国家开始看起来像神经网络。也就是说，这些国家被建造成多层结构，每一层可能包含许多城市。它们只有一个入口和一个出口。 现有恰好 $L$ 层，每层有 $N$ 个城市。我们来看相邻的两层 $L_1$ 和 $L_2$。第 $L_1$ 层的每个城市都与第 $L_2$ 层的每个城市相连，从 $L_1$ 的城市 $i$ 到 $L_2$ 的城市 $j$ 的通行费用为 $c_{ij}$。每对相邻层之间的城市连接费用都相同（即所有相邻层之间的连接方式完全一样）。另外，对于从 $L_1$ 到 $L_2$ 的所有城市 $i$，到固定城市 $j$ 的费用 $c_{ij}$ 都是相同的（即对于固定 $j$，$c_{ij}$ 相同）。 Doctor G. 需要加速他在这个国家中的计算，因此他请你计算从入口到出口可以选择多少条路径，使得它们的总通行费用能被给定数 $M$ 整除。

输入的第一行包含 $N\ (1\leq N \leq 10^{6})$，$L\ (2\leq L \leq 10^{5})$ 和 $M\ (2\leq M \leq 100)$，分别表示每层城市数量、层数以及所要求的可整除的数。 接下来的三行每行包含 $N$ 个整数，分别表示从入口到第一层的费用（$0 \leq cost \leq M$）、相邻层之间的费用（如描述中所述，每层对之间的费用相同）、以及从最后一层到出口点的费用。

输出一个整数，表示 Doctor G. 可以选择的路径数，使得总费用能被 $M$ 整除，结果对 $10^9+7$ 取模。

下图展示的是一个有 $3$ 层、每层 $2$ 个城市的国家。路径 $(1,1,2)$ 和 $(2,2,1)$ 是仅有的总费用能被 $13$ 整除的路径。注意，每层之间的输入边费用都相同，且各层之间的连接方式完全一致。 由 ChatGPT 5 翻译