ll@n,@p,@a[n],q=1,z=0;
while(q*=p,q<1d9){
	HashMap<int,int>h;
	h.init(min(q,n),0);
	rep(i,n){
		z+=h[a[i]%q]++;
	}
}
wt(z);