1170 - 和为K的倍数
描述

小b喜欢和为K的倍数的序列。

现在有一个长度为n的序列A,请问A有多少个非空连续子序列是小b喜欢的。


输入

第一行输入一个正整数n; 第二行输入n个整数,表示A[i],以空格隔开; 第三行输入一个正整数K; 其中1≤n≤30000,对于任意A[i]有-10000≤A[i]≤10000,2≤K≤10000


输出

输出一个数,表示子序列的数目


样例

输入

6
4 5 0 -2 -3 1
5

输出

7
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 57
通过次数 18