# Subarrays with sum divisible by n

Given an array of

`n`

numbers, you would like to know how many subarrays are there that have a sum divisible by `n`

. Input

The first line of the input contains two integers -

`n`

the number of elements in the array (1 β€ n β€ ). The following line contains

`n`

integers separated by a space, that represent the elements of the array . Output

The program should print a single integer - the number of subarrays whose sum is divisible by

`n`

. Examples

Input | Output |

5
5 2 3 4 6 | 6 |

Explanation

`5`

`2 3 4 6`

`5`

`2 3`

`4 6`

`5 2 3`

`4 6`

`5 2 3`

`4 6`

`5`

`2 3 4 6`

`5 2 3 4 6`

Β

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB