Question

Count Subarrays with Sum Divisible by K

You are given an array of N integers and an integer K.

Count the number of subarrays whose sum is divisible by K.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.

Output

Print a single integer — the number of subarrays whose sum is divisible by KaTeX can only parse string typed expression.

Example

Example:
Input

5 3

1 2 3 1 2

Output

Online