Hello ah, I am gray little ape, a super will write bug program ape!

Welcome to my column.”The daily blue bridge”, the main role of this column is to share with you in recent years blue bridge cup provincial competition and the final and other real questions, analysis of the existing algorithm ideas, data structure and other content, to help you learn more knowledge and technology!

Title: K times interval

Given a sequence of length N, A1,A2… A N, if A continuous subsequence A I,A I +1… The sum of A and j is multiples of K, so let’s say the interval [I,j] is K times the interval.

Can you figure out how many K intervals there are in this sequence?

Input format

The first line