由于最近深度学习的流行,新的国家开始看起来像神经网络。也就是说,国家正在多层构建,每层可能有许多城市。它们还有一个入口和一个出口。
正好有 L 层,每层有 N 个城市。让我们看看两个相邻的层 L1 和 L2。 L1 层中的每个城市都与 L2 层中的每个城市相连,行驶成本 cij 为 $$i,j\in\{1,2,\ldots,N\}$$,并且每对相邻层在其城市之间的成本与任何其他对相同(它们只是像往常一样堆叠相同的层)。此外,对于 L1 中的所有城市,从 L2 层到每个城市的旅行成本是相同的,即 cij 对于 $$i \in \{1, 2, \ldots, N\}$$ 和固定 j 来说是相同的。
G. 博士需要加快对该国家/地区的计算速度,因此他要求您找到他从入境点到出境点可以采取的路径数,以便他的旅行成本可以除以给定的数字 M。
输入
输入的第一行包含 N (1 ≤ N ≤ 106)、L (2 ≤ L ≤ 105) 和 M (2 ≤ M ≤ 100),分别为每层中的城市数量、层数和出行成本应整除的数量。
第二、第三和第四行包含N个整数,每个整数表示从入口点到第一层的成本0≤成本≤M、如上所述的相邻层之间的成本以及从最后一层到出口点的成本。
输出
输出一个整数,即医生 G. 可以采取的总成本可被 M(模 109 + 7)整除的路径数。
示例
输入 #1
2 3 13 4 6 2 1 3 4
输出 #1
2
注意
这是一个有3层的国家,每层有2个城市。路径 $$6 \rightarrow 2 \rightarrow 2 \rightarrow 3$$ 和 $$6 \rightarrow 2 \rightarrow 1 \rightarrow 4$$ 是总成本可被 13 整除的唯一路径。请注意,图层城市的输入边具有相同的成本,并且它们对于所有图层都相同。