题目内容

给定一个整数序列 $a$ ，以及 $2$ 个整数 $x$ ，$k$ 。

求出有多少区间$[L, R](L <= R)$，使得该区间中恰好有 $k$ 个$a_i(L <= i <= R)$满足 $a_i$ 能被 $x$ 整除。

时间限制：1000ms

内存限制：262mb

输入描述

$1 <= length(a), x <= 10^5$ $0 <= k <= 10^5$

输出描述

返回答案

样例1

输入

1 2 3 4
2 1

输出

6

说明

总共有 $6$ 个区间，满足恰好有 $1$ 个数被 $2$ 整除。

$[1,2],[1,3],[2,2],[2,3],[3,4],[4,4]$ 。