题目描述

给定一个长度为 n 的整数数组 arr，以及两个整数 k 和 m。你需要找出数组中所有连续子数组，满足以下条件：

1、子数组中质数的个数为奇数。

2、子数组中所有元素的前缀和（从子数组起始位置到当前位置的元素和）中，有至少 m 个前缀和能被 k 整除。

输入格式

第一行包含三个整数 n、k 和 m，分别表示数组的长度、整除的除数以及能被 k 整除的前缀和的最少数量。

第二行包含 n 个整数，表示数组 arr 的元素。 输出格式

输出一个整数，表示满足条件的连续子数组的数量。

样例输入

5 3 2

2 3 4 5 6

样例输出

1