题目描述

给定一个长度为 $n$ 的数组 $a_i$，统计有多少子区间 $[l,r](l\leq r)$，满足 $\displaystyle\sum_{i=l}^r a_i \equiv x\pmod{m}$。

输入格式

第一行三个整数 $n,m,x$，由空格隔开。

接下来第二行有 $n$ 个整数 $a_i$。

输出格式

仅一行，为满足条件的子区间的个数。

样例

样例输入

9 9 6
0 3 5 2 5 1 4 0 4

样例输出

5

样例解释

满足条件的区间为：a[0,4],a[0,8],a[1,4],a[1,8],a[4,5]

数据范围与提示

$1 \leq n \leq 10^5$

$1 \leq m \leq 10^9$

$0 \leq x,a_i < m$