Given a sequence of N integers a1, a2, ..., aN, any contiguous segment of elements in the original sequence is called a subarray. Two subarrays are considered different if there exists at least one element that belongs to one subarray but not the other.

For example, in the sequence {a1, a2, a3, a4}, the subarrays are: {a1}, {a2}, {a3}, {a4}, {a1, a2}, {a2, a3}, {a3, a4}, {a1, a2, a3}, {a2, a3, a4}, {a1, a2, a3, a4}.

The task is to count the number of subarrays such that the sum of the M-th powers of the elements in the subarray is divisible by K. first line : N,M,K (1 ≤ N ≤ 10^5; 1 ≤ M ≤10^18,1 ≤ K ≤ 10^5) second line : a1,a2,..an (1 ≤ ai ≤ 10^50)

inp: out 4 1 3 4 3 2 1 5