Dat je niz ~A~ dužine ~N~. Takođe, dat je prirodan broj ~L~, tako da je ~N~ uvek deljivo sa ~L~. Niz ~A~ podelimo na ~L~ grupa, gde je svaka grupa sačinjena od elemenata čiji indeksi daju iste ostatke pri deljenju sa ~L~.

Na koliko načina se mogu izabrati indeksi ~i~ i ~j~, gde važi ~1 \leq i < j \leq N~, tako da nakon što razmenimo elemente niza ~A~ sa ovim indeksima, važi da je suma svih grupa jednaka?

Opis ulaza

Prva linija standardnog ulaza sadrži dva prirodna broja ~N~, ~L~ odvojena razmakom. Naredna linija sadrži ~N~ elemenata odvojenih razmakom - niz ~A~.

Opis izlaza

U prvu i jedinu liniju standardnog izlaza ispisati traženo rešenje.

Primer 1

Ulaz

4 2
1 5 3 3

Izlaz

2

Primer 2

Ulaz

6 2
1 2 3 4 5 6

Izlaz

0

Objašnjenje primera

U prvom primeru jednu grupu čine elementi čiji indeksi daju ostatak ~0~ pri deljenju sa ~2~, i to su indeksi ~2,4~ na kojima se nalaze brojevi ~A_2=5,A_4=3~, dok drugu grupu čine elementi čiji indeksi daju ostatak ~1~ pri deljenju sa ~2~, i to su indeksi ~1,3~ na kojima se nalaze brojevi ~A_1=1,A_3=3~. Možemo razmeniti elemente sa indeksima 2 i 3, ili elemente sa indeksima 1 i 4.

U drugom primeru ne postoji ni jedan način da razmenom dva elementa dobijemo da dve grupe imaju jednaku sumu.

Ograničenja

U svim test primerima važi:

• ~1 \leq N \leq 200000~
• ~0 \leq A_i \leq 2 \cdot 10^6~.

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 20 poena: ~N \leq 10~ i ~A_i \leq 500~.
• U test primerima vrednim 20 poena: ~N \leq 100~ i ~A_i \leq 500~.
• U test primerima vrednim 20 poena: ~A_i \leq 500~.
• U test primerima vrednim 40 poena: Nema dodatnih ograničenja.