Problem10954--小光的难题

10954: 小光的难题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

小光现在有一个长度为 $n$ 的序列,他想从中间挑一串连续的子序列,使得他们的和与 $m$ 取余为 $0$。
小光发现,这样情况太多了,数都数不过来。
于是小光想请你帮忙解决这个问题。

Input

输入有两行。
第一行包括两个数字 $n,m\ (1 \leq n,m \leq 2\times 10^5)$。
第二行包括 $n$ 个数字,每个数都是正整数且小于 $10^7$。

Output

输出一个整数,表示答案。

Sample 1 Input

5 3
1 2 3 4 5

Sample 1 Output

7
符合条件的子序列有 7 个。具体如下
{1,2},{1,2,3},{1,2,4,4,5}
{2,3,4},
{3},{3,4,5}
{4,5}

Sample 2 Input

10 17
17 17 17 17 17 17 17 17 17 17

Sample 2 Output

55

Sample 3 Input

14 13
8 15 13 18 19 10 6 5 14 12 3 12 19 1 

Sample 3 Output

5

EDITORIAL

Source/Category