Subarray con somma divisibile per n

Dato un array di n numeri, si desidera sapere quanti subarray hanno una somma divisibile per n.

Input

La prima riga dell’input contiene due numeri interi: n, il numero di elementi dell’array (1 ≤ n ≤ ).

La riga successiva contiene n interi separati da uno spazio, che rappresentano gli elementi dell’array .

Output

Il programma deve stampare un singolo intero: il numero di subarray la cui somma è divisibile per n.

Esempi

Spiegazione

1. 5 2 3 4 6

2. 5 2 3 4 6

3. 5 2 3 4 6

4. 5 2 3 4 6

5. 5 2 3 4 6

6. 5 2 3 4 6